数论筛法学习笔记-526互联

算法部分

杜教筛

\[S(n) = \sum_{i = 1}^{n}f(i) \]

要求 \(f\)积性，且能被表示为 \(f* h = g\)，而 \(g\) 的前缀和与 \(h\) 的点值是好求的。

考虑展开狄利克雷卷积。

\[\begin{aligned} \sum_{i = 1}^{n} f* h(i) &= \sum_{i = 1}^{n}\sum_{d|i}f(d)h \left( \frac{i}{d} \right) \\ &= \sum_{ i= 1}^{n}\sum_{d | i}f \left(\frac{i}{d}\right)h(d) \\ &= \sum_{d = 1} ^ {n}\sum_{i = 1}^{\lfloor{\frac{n}{d}}\rfloor}f(i)h(d) \\ &= \sum_{d = 1} ^{n}h(d)S\left(\left \lfloor{\frac{n}{d}}\right \rfloor \right)\end{aligned} \]

整理一下，获得

\[S_f(n) = S_g(n) - \sum_{d = 2}^{n}h(d)S \left(\left \lfloor \frac{n}{d}\right \rfloor \right) \]

使用类似整除分块的方法，可以只需要求出\(\mathcal O(\sqrt n)\) 个点值，经过积分分析，时间复杂度为 \(\mathcal O(n^{\frac{3}{4}})\)。如果通过线性筛筛出较小的值，较大的值递归计算的话，时间复杂度可被优化至 \(\mathcal O(n^{\frac{2}{3}})\)。

PN筛

考虑构造积性函数 \(g(p)=f(p)[p\text{ is }prime]\)，若 \(g\) 的块筛容易获得，则我们也可以获得 \(f\) 的块筛。

考虑函数 \(h\) 满足 \(f = g * h\)，则由于狄利克雷卷积对积性函数构成一个群，\(h\) 同为积性函数，而由于 \(f(p) = g(p) + h(p)\) ，则 \(h(p)\) 处为 \(0\)，且由于积性性质，若有 \(p | n,p^2\not|n,h(n) = 0\)，所以有值的 \(h\) 并不多，我们将其称之为 \(PN\)(Powerful Number)。

显然，所有 \(PN\) 可被表示为 \(a^2b^3\)，而通过积分分析，小于 \(n\) 的 \(PN\) 只会有 \(\mathcal O(\sqrt n)\) 个，通过 \(dfs\) 找出所有 \(PN\) 的复杂度相同。

进行一波与杜教筛类似的推导。

\[\begin{aligned} S_f(n) &= \sum_{i = 1}^{n} \sum_{d|i}g \left(\frac{i}{d} \right)h(d) \\ &= \sum_{d = 1}^{n}\sum_{i = 1}^{\left \lfloor \frac{n}{d} \right \rfloor}g(i)h(d) \\ &= \sum_{d = 1} ^ {n}S_g\left( \left \lfloor \frac{n}{d}\right \rfloor \right) h(d)\end{aligned} \]

由于只有在 \(PN\) 处 \(h\) 有值，所以只要求得 \(g\) 的块筛就可以在 \(\mathcal O(\sqrt n)\) 的时间内求得 \(f\) 的块筛。实际应用中，瓶颈往往在求得 \(g\) 的块筛而不是 \(PN\) 筛。