杜教筛的作用是可以快速求出积性函数的前缀和，相比于传统的线性筛，杜教筛可以在\(O(n^{2/3})\)的时间求出积性函数的前缀和。
什么是积性函数呢？若a⊥b（a,b互质），那么有\(f(ab)=f(a)f(b)\) 则称\(f(x)\)的积性函数。
定义两个积性函数的狄利克雷卷积为\((f*g)(i)=\sum_{d|n}f(d)\)$*g(\frac{d}{n}) $
给出几个常见的狄利克雷卷积的结论
(\(I(x)=1,id(x)=x,\epsilon(x)=[x==1]\))
1.\(\mu*I=\epsilon\)
证明：\(\mu*I=\sum_{d|n}\mu(d)*I(\frac{n}{d})=\sum_{d|n}\mu(d)=[n==1]=\epsilon\)
2.\(φ*I=id\)
证明：\(φ*I=\sum_{d|n}φ(d)*I(\frac{n}{d})=\sum_{d|n}φ(d)=n=id(n)\)
对于倒数第二步，考虑统计与\(n\)的\(gcd\)分别为\(1,2,...,n\)的过程：
对于\(1-n\)所有数，与\(n\)的\(gcd\)为\(1\)的有\(φ(n)\)个；若\(2|n\)，则与\(n\)的\(gcd\)为2有\(φ(\frac{n}{2})\)个……以此类推，总共有\(n\)个数，故\(\sum_{d|n}φ(d)=n\)
3.\(id*\mu=φ\)
证明：\(id*\mu=\sum_{d|n}\mu(d)*\frac{n}{d}=φ\)
对于最后一步，统计1-n与n互质的数的个数，然后容斥一下即可。
设积性函数f,g，令\(S(n)=\sum_{i=1}^{n}f(i)\)
\(\sum_{i=1}^{n}(f*g)(i)=\sum_{i=1}^{n}\sum_{d|n}f(d)*g(\frac{n}{d})=\sum_{i=1}^{n}g(i)*\sum_{j=1}^{[\frac{n}{i}]}f(j)=\sum_{i=1}^{n}g(i)*S(\frac{n}{i})\)
移向得：\(g(1)*S(n)=\sum_{i=1}^{n}(f*g)(i)-\sum_{i=2}^{n}g(i)*S(\frac{n}{i})\)
\(S(n)=\frac{\sum_{i=1}^{n}(f*g)(i)-\sum_{i=2}^{n}g(i)*S(\frac{n}{i})}{g(1)}\)
我们发现，S(n)是我们所求，我们把S(n)拆成了递归形式，假设我们可以求出\(\sum_{i=1}^{n}(f*g)(i)\)，\(g(x)\)，我们就可以对\(\sum_{i=2}^{n}g(i)*S(\frac{n}{i})\)进行整除分块，从而递归求出\(S(N)\)！
原文：https://www.cnblogs.com/bcoier/p/10362913.html