杜教筛
杜教筛作用：
以\(O(n^{\frac{2}{3}})\)的时间复杂度求出积性函数的前缀和
具体方法：
如要求：\(S(n)=\sum\limits_{i=1}^nf(i)\)
先任取一个积性函数\(g(n)\)与\(f(n)\)卷积一下，得到：
-
\((f*g)(n)=\sum\limits_{d|n}g(d)f(\dfrac{n}{d})\) ， 对该卷积求前缀和，得到：
-
\(\sum\limits_{i=1}^n(f*g)(i)=\sum\limits_{i=1}^n\sum\limits_{d|i}g(d)f(\dfrac{i}{d})\) ，改变枚举顺序，把\(g(d)\)提到前面来，可得：
-
\(=\sum\limits_{d=1}^ng(d)\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i)\) ，再代入\(S\)函数：
-
\(=\sum\limits_{d=1}^ng(d)S(\lfloor\dfrac{n}{d}\rfloor)\)
-
于是我们得到了 \(\sum\limits_{i=1}^n(f*g)(i)=\sum\limits_{i=1}^ng(i)S(\lfloor\dfrac{n}{i}\rfloor)\) (换成\(i\)舒服一点...)
然后显然有 \(g(1)S(n)=\sum\limits_{i=1}^ng(i)S(\lfloor\dfrac{n}{i}\rfloor)-\sum\limits_{i=2}^ng(i)S(\lfloor\dfrac{n}{i}\rfloor)\)
把上面推得的式子代入可得：\(g(1)S(n)=\sum\limits_{i=1}^n(f*g)(i)-\sum\limits_{i=2}^ng(i)S(\lfloor\dfrac{n}{i}\rfloor)\)
假如我们要求的是 \(\sum\limits_{i=1}^n\mu(i)\)，把\(f\)换成\(\mu\)
\(g(1)S(n)=\sum\limits_{i=1}^n(\mu*g)(i)-\sum\limits_{i=2}^ng(i)S(\lfloor\dfrac{n}{i}\rfloor)\)
因为我们知道 \(\mu * 1 = ϵ\)，如果把 \(g\) 用 \(1\) 代入，那么\(g(1)=1\)，\(\sum\limits_{i=1}^nϵ(i)=1\)，\(\sum\limits_{i=2}^n1(i)=1\)
整个式子会变得十分美妙~
- 即为 \(S(n)=1-\sum\limits_{i=2}^nS(\lfloor\dfrac{n}{i}\rfloor)\)