筛法
本文不作为教学向文章。
冷静分析：CMD 的博客
线性筛
线性筛是个好东西。一般来说，可以在 $O(n)$ 内处理几乎所有的积性函数。
还可以 $O(n)$ 找出所有的质数……（废话
杜教筛
放在偏序关系 $(\Z, |)$ 中卷积……
如何快速的求 $S(n) = \sum_{i = 1}^n f(i)$。
如果能够找到一个函数 $g$ ：
$$\begin{aligned} \sum_{i = 1}^n (f * g)(i) &= \sum_{i = 1}^n \sum_{d | i} f(\frac id) g(d) \\ &= \sum_{d = 1}^{n} g(d) \sum_{i = 1}^{\lfloor \frac nd \rfloor} f(i) \\ &= \sum_{d = 1}^{n} g(d) S(\lfloor \frac nd \rfloor) \\ \end{aligned} $$
那么可以得出：
$$g(1)S(n) = \sum_{i = 1}^n (f * g)(i) - \sum_{d = 2}^n g(d) S(\lfloor \frac nd \rfloor) $$
这样我们就可以通过整除分块快速的求出 $g(1) S(n)$ 了。
当然，需要有很严苛的前提：
$f * g$ 的前缀和是可以快速求的。
$g$ 的前缀和也是可以快速求的。
这里的快速应该是 $O(1)$，如果是 $O(\log n)$ 估计也没关系。
其时间复杂度大概是在 $O(n^{\frac 23})$ 的，如果不预处理小块的话应该是 $O(n^{\frac 34})$ 的。
例题：
快速求 $\sum_{i = 1}^n \sum_{j = 1}^n \varphi(\gcd(i, j))$
快速求 $\sum_{i = 1}^n \sum_{j = 1}^n i \cdot j \cdot gcd(i, j)$
例二中有一个很好的东西，点乘。
其定义有：$(f \cdot g)(n) = f(n) \cdot g(n)$。
当 $h$ 为完全积性函数时，有 $(f \cdot h) * (g \cdot h) = (f * g) \cdot h$。
这里列出一些基本的组合：
$\mu \cdot id_k$
有 $((\mu \cdot id_k) * id_k)(n) = \sum_{d | n} \mu(d) d^k (\frac nd)^k = n^{k + 1}\sum_{d | n} \mu(d) = \varepsilon(n)$
$\varphi \cdot id_k$
有 $(\varphi \cdot id_k) * id_k = I$，推导同上。
Min25 筛
本质是对线性筛的扩展……
为了方便，声明一些符号：
$P$ 代表质数集合。
$P_i$ 表示第 $i$ 个质数。
$minp(i)$ 表示 $i$ 的最小质因数。
还是求 $\sum_{i = 1}^n f(i)$。可以用 Min25 筛需要满足一些条件：
$f(i)$ 是一个低阶多项式。
$f(p^k)$ 可以快速的求解。
现在考虑把每一阶分别计算。
PN 筛
首先定义 Powerful Number。
一个数是 Powerful Number 当其质因数分解中 $n = \prod_{i = 1}^k p_i^{c_i}$，$\forall i(c_i > 1)$。
由于一个 Powerful Number 可以表示为一个数的平方和一个数的立方，所以 $n$ 以内的 PN 数一共有 $O(\sqrt n)$ 个。
现在假设要求 $F(n) = \sum_{i = 1}^n f(i)$。
需要找到函数 $g$ 满足：
为积性函数。
易求前缀和。
在质数 $p$ 处取值与原函数相等：$f(p) = g(p)$。
记 $G(n) = \sum_{i = 1}^n g(n)$。
先构造函数 $h$ 满足 $h * g = f$。
于是将卷积展开：
$$\begin{aligned} F(n) &= \sum_{i = 1}^n f(i) = \sum_{i = 1}^n \sum_{d | i} h(d) g(\frac id) \\ &= \sum_{d = 1}^{n} \sum_{i = 1}^{\lfloor \frac nd \rfloor} h(d) g(i) \\ &= \sum_{d = 1}^n h(d) \sum_{i = 1}^{\lfloor \frac nd \rfloor} g(i) \\ &= \sum_{d = 1}^n h(d) G(\lfloor \frac nd \rfloor) \end{aligned} $$
怎么可以套数论分块？
由于积性函数相乘任然为积性函数，所以可知 $h(1) = 1$。
所以对于质数 $p$，有 $f(p) = g(1)h(p) + g(p)h(1) = h(p) + g(p)$。
由于 $f(p) = g(p)$，所以可知 $h(p) = 0$。
根据积性函数的性质，可以推导出 $h(n)$ 只在 $n$ 为 PN 数的时候才可能不为 $0$。
所以原式变为：
$$F(n) = \sum_{\text{d is PN}}^{n} h(d) G(\lfloor \frac nd \rfloor) $$
这样，我们只需要求出 $O(\sqrt n)$ 个 $h(d)$ 的取值，以及快速算出 $G(x)$ 的取值即可。
那么我们考虑如何求解 $h(d)$？
根据 $f = g * h$ 有
$$f(p^c) = \sum_{i = 0}^c g(p^i)h(p^{c - i}) $$
稍微移项可以得到：
$$g(1)h(p^c) = f(p^c) - \sum_{i = 1}^c g(p^i)h(p^{c - i}) \\ \downarrow \\ h(p^c) = f(p^c) - \sum_{i = 1}^c g(p^i)h(p^{c - i}) $$
于是可以枚举所有的 $p$ 以及 $c$ 求出 $h(p^c)$ 即可。
此时 $p$ 的个数视作 $O(\sqrt n)$，而 $c$ 的界为 $O(\log n)$，有由于是 $\log n$ 转移，所以这部分复杂度为 $O(\sqrt n \log n^2)$，而且这个上界很宽松。
但是如果我们直接推导出 $h(p^c)$ 仅与 $p^c$ 有关的计算公式，那么可能更加优秀，复杂度一般为 $O(\sqrt n \log n)$。
所以总的复杂度一般为 $O(\sqrt n + \sqrt n \log n) = O(\sqrt n \log n)$。非常的优秀。
然而根据 CMD 的博客，硬上的复杂度实际上是 $O(\sqrt n / \log n)$……更加优秀了。
不过有些情况下，利用 PN 筛可能需要套一个杜教筛，毕竟我们除了 $h(p^c)$ 还需要求出 $G(x)$ 的前缀和。
此时需要加上杜教筛的复杂度，可以认为是 $O(n^{\frac 23})$ 的。