本文不作为教学向文章。
线性筛是个好东西。一般来说，可以在 \(O(n)\) 内处理几乎所有的积性函数。
还可以 \(O(n)\) 找出所有的质数……（废话
放在偏序关系 \((\Z, |)\) 中卷积……
如何快速的求 \(S(n) = \sum_{i = 1}^n f(i)\)。
如果能够找到一个函数 \(g\) ：
那么可以得出：
这样我们就可以通过整除分块快速的求出 \(g(1) S(n)\) 了。
当然，需要有很严苛的前提：
\(f * g\) 的前缀和是可以快速求的。
\(g\) 的前缀和也是可以快速求的。
这里的快速应该是 \(O(1)\)，如果是 \(O(\log n)\) 估计也没关系。
例题：
快速求 \(\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\)，推导同上。
本质是对线性筛的扩展……
为了方便，声明一些符号：
\(P\) 代表质数集合。
\(P_i\) 表示第 \(i\) 个质数。
\(minp(i)\) 表示 \(i\) 的最小质因数。
还是求 \(\sum_{i = 1}^n f(i)\)。可以用 Min25 筛需要满足一些条件：
\(f(i)\) 是一个低阶多项式。
\(f(p^k)\) 可以快速的求解。
现在考虑把每一阶分别计算。
首先定义 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\)。
于是将卷积展开：
怎么可以套数论分块？
由于积性函数相乘任然为积性函数，所以可知 \(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\)。
所以原式变为：
这样，我们只需要求出 \(O(\sqrt n)\) 个 \(h(d)\) 的取值，以及快速算出 \(G(x)\) 的取值即可。
那么我们考虑如何求解 \(h(d)\)？
根据 \(f = g * h\) 有
稍微移项可以得到：
于是可以枚举所有的 \(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)\)。非常的优秀。