杜教筛

杜教筛用来解决积性函数前缀和的问题，可以在低于线性的时间复杂度内求出前缀和

求欧拉函数前缀和

记欧拉函数前缀和 $f(n)=\sum_{i=1}^{n}\phi(i)$
已知 $\sum_{d|n}{\phi(d)}=n$
所以 $\sum_{i=1}^{n}\sum_{d|i}\phi(d)=\frac{n(n+1)}{2}$
先枚举 $d$ 则原式等于 $\sum_{d=1}^{n}\sum_{k=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\phi(k)=\frac{n(n+1)}{2}$
$*$ 上面一步相当于先枚举其中一个因子为 $d$ ,则只要 $dk\le n$ 那么 $k$ 就一定是 $[1,n]$ 中某个数的因子，而原式的含义就是将 $[1,n]$ 中所有数的因子的 $\phi$ 相加
然后我们发现 $\sum_{d=1}^{n}\sum_{k=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\phi(k)=\sum_{d=1}^{n}f(\left\lfloor\frac{n}{d}\right\rfloor)=\frac{n(n+1)}{2}$
所以 $f(n)=\sum_{d=1}^{n}f(\left\lfloor\frac{n}{d}\right\rfloor)-\sum_{d=2}^{n}f(\left\lfloor\frac{n}{d}\right\rfloor)=\frac{n(n+1)}{2}-\sum_{d=2}^{n}f(\left\lfloor\frac{n}{d}\right\rfloor)$
右边部分可以预处理大约 $\sqrt{n}$ 个，再用整除分块解决

求莫比乌斯函数前缀和

和求欧拉函数前缀和一样，记前缀和 $f(n)=\sum_{i=1}^{n}\mu(i)$
所以 $\sum_{d|n}\mu(d)=\epsilon(n)$
则 $\sum_{i=1}^{n}\sum_{d|i}=1$
$*$ 显然只有 $i$ 取 $1$ 的时候后面值为 $1$ ，其余都是 $0$
参照上面，最后可以化简为 $f(n)=1-\sum_{d=2}^{n}f(\left\lfloor\frac{n}{d}\right\rfloor)$
同样预处理 $\sqrt{n}$ 个，然后整除分块处理

对于一般的积性函数

记 $g(n)=\sum_{d|n}h(n)$
$f(n)=\sum_{i=1}^{n}h(i)$
则 $f(n)=g(n)-\sum_{d=2}^{n}f(\left\lfloor\frac{n}{d}\right\rfloor)$

数学 杜教筛

杜教筛

求欧拉函数前缀和

求莫比乌斯函数前缀和

对于一般的积性函数

数学杜教筛