算法学习笔记(28): 筛法
筛法
线性筛
杜教筛
放在偏序关系 \((\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\)，推导同上。
Min25 筛
本质是对线性筛的扩展……
为了方便，声明一些符号：
-
\(P\) 代表质数集合。
-
\(P_i\) 表示第 \(i\) 个质数。
-
\(minp(i)\) 表示 \(i\) 的最小质因数。
还是求 \(\sum_{i = 1}^n f(i)\)。可以用 Min25 筛需要满足一些条件：
-
\(f(i)\) 是一个低阶多项式。
-
\(f(p^k)\) 可以快速的求解。
现在考虑把每一阶分别计算。