tqyaaaaang's Blog

AUTHOR: Tianqi Yang

tqyaaaaang's Blog.

Navigation

洲阁筛

来讲讲求某些积性函数前缀和的黑科技。 这次讲洲阁筛。 推荐任之洲的2016年国家集训队论文。 前置技能 你需要知道下列东西来理解洲阁筛,这里就不详细讲了,百度一下应该会有很多的好的博客的,或者上面的论文中也有提到。 数论函数 积性函数 狄利克雷卷积 洲阁筛 不得不说,洲阁筛比杜教筛要麻烦,但是适用范围更广。 洲阁筛要求对于任意质数 \(p\),\(f(p)\) 为一个关于 \(p\) 的低阶多项式,再对于满足 \(f(p^c) \le n\) 的任意指数 \(c\),\(f(p^c)\)可以较快速算出,则洲阁筛可以在\(\Theta(\frac{n^{\frac{3}{4}}}{\log{n}})\)复杂度内求出 $$ F(n) = \sum_{i=1}^n{f(i)} $$ 一些规定 设小于等于\(\sqrt{n}\)的质数有\(m\)个,升序排列后设为\(p_1, p_2, p_3, \ldots, p_m\)。这个可以线性筛\(\Theta{\sqrt{n}}\)预处理。 设集合\(S\…

杜教筛

来讲讲求某些积性函数前缀和的黑科技。 推荐一篇博客: 浅谈一类积性函数的前缀和 前置技能 你需要知道下列东西来理解杜教筛,这里就不详细讲了,百度一下应该会有很多的好的博客的,或者上面的博客中也有提到。 数论函数 积性函数 常见的积性函数以及其性质 ( \(\varphi(n)\), \(\mu(n)\) ) 狄利克雷卷积 杜教筛 先来看一下常见的积性函数的前缀和。 \(\varphi(n)\) 令 \(\phi(n) = \sum_{i=1}^n{\varphi(i)}\) 欧拉函数的前缀和应该是最经典的了。 首先要知道 \(\sum_{d|n}{\varphi(n)} = n\) 然后就可以转化: $$ \phi(n) = \sum_{i=1}^n{\varphi(n)} = \sum_{i=1}^n{(i - \sum_{d|i, d \ne i}{\varphi(d)})} = \sum_{i=1}^n{i} - \sum_{i=1}^n { \sum_{d|i, d \ne i}…

Anniversary Cup #1 Day 1(LibreOJ Round #9)

A. ZQC 的迷宫 ( LOJ 559 ) 题目链接:https://loj.ac/problem/559 常识题,不说了,沿着墙一定能走出迷宫 代码 #include <bits/stdc++.h> using namespace std; #define LL long long #define LD long double #define SC(t,x) static_cast<t>(x) #define AR(t) vector < t > #define PII pair < int, int > #define PLL pair < LL, LL > #define PIL pair < int, LL > #define PLI pair < LL, int…

UOJ - 126 - 快餐店 ( 环套树DP )

题目链接:http://uoj.ac/problem/126 详细题解在代码后面 思路 环套树DP(废话) 考虑树的情况怎么做 考虑如何拓展到环上 代码 #include <iostream> #include <sstream> #include <fstream> #include <iomanip> #include <cstdio> #include <cstdlib> #include <cmath> #include <vector> #include <deque> #include <list> #include <set> #include <map> #include <stack> #include <queue> #include <bitset> #include <algorithm&…

HDU 4914 ( 特征多项式+FFT )

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=4914 题意 给定n, a, b, p, q,定义\(f(k)\)如下: $$ f(k)= \begin{cases} 1 & k <= 0 \\ a * f(k-p) + b * f(k-q) & k > 0 \end{cases} $$ 求\(f(n)\)。 解法 模板题。用特征多项式优化一下矩阵乘法,然后用FFT优化多项式乘法就行了。 不会特征多项式的看这里 代码 #include <bits/stdc++.h> using namespace std; #define LL long long #define LD long double #define SC(t,x) static_cast<t>…