杜教筛
参考来源： OI-Wiki， 网上博客
线性筛可以在线性时间求积性函数前缀和， 而杜教筛可以用低于线性时间求解积性函数前缀和。
我们考虑 \(S(n)\) 就是积性函数的前缀和， 所以我们尝试构造关于 \(\large S(n)\) 关于 \(\large S(\lfloor \frac{n}{i} \rfloor)\) 的递推式。
对于任意一个数论函数 g，必满足：
\(\begin{aligned} \sum_{i=1}^{n}(f * g)(i) & =\sum_{i=1}^{n}\sum_{d \mid i}g(d)f\left(\frac{i}{d}\right) \\ & =\sum_{i=1}^{n}g(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right) \end{aligned} \)
将 \(\large S(n)\) 提出来就可以得到：
\(\begin{aligned} g(1)S(n) & = \sum_{i=1}^n g(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right) - \sum_{i=2}^n g(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right) \\ & = \sum_{i=1}^n (f * g)(i) - \sum_{i=2}^n g(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right) \end{aligned} \)
再将 \(g(1)\) 移过去即可得到 \(S(n)\) 的递推式， 考虑我们可以自己构造 \(g(n)\) 使得计算变快。
当我们构造出这样的 \(g(n)\) 时：
- 可以快速计算 \(\sum_{i=1}^n(f * g)(i)\)；
- 可以快速计算 g 的前缀和，以用数论分块求解 \(\sum_{i=2}^ng(i)S\left(\left\lfloor\dfrac{n}{i}\right\rfloor\right)\)。
则我们可以在较短时间内求得 \(g(1)S(n)\)。