好久以前就写过了，但是现在才搞懂原理。
前置知识
首先称一个函数 (f(x)) 为 积性函数 ，当且仅当对于任意两个互质的数 (a,b) ，有：
更特殊地，称一个函数 (f(x)) 为 完全积性函数 ，当且仅当对于任意 (a,b) ，有：
常见的积性函数有 (mu,varphi,sigma,d) ，完全积性函数有：(epsilon,I,id)
(epsilon(n)=[n=1],I(n)=1,id(n)=n)
对于两个函数 (f,g) ，定义他们的 迪利克雷卷积 为：
对于上面我们已经给出函数，有这样一些卷积关系是：
补充一个东西，(sum_{x|n}varphi(x)=n) 的证明，考虑两个互质的数 (m,n) ，有：
这说明了 (f(x)=sum_{x|n}varphi(x)) 是一个积性函数，对于质数有 (f(p_i^{k_i})=p_i^{k_i}) ，那么 (f(n)=n)
杜教筛
他是用来解决这样一个问题：$$sum_{i=1}^nf(i)=S(n)$$ ，做法是找一个 辅助函数 (g) ，也就是我们先求出 (f*g) 的前缀和，再算 (f) 的前缀和，选取 (g) 的标准就是 (f*g) 和 (g) 的前缀和都是很好算的 ，先来推柿子：
然后套路地枚举 (d) （这种东西莫比乌斯反演的时候都见惯了）：
考虑 用前缀和来表示单个项 (g(1)S(n)) ，因为前缀和是好算的：
假定前面的项是好算的，后面的项可以用数论分块来解决，容易发现我们得到了一个递归的问题。
模板题
(mu) 的前缀和
考虑到莫比乌斯反演的那个柿子：(mu*I=epsilon) ，令 (f=mu,g=I,f*g=epsilon)
ll get_mu(int n)
{
if(n<=N) return mu[n];//这里是预处理的mu
if(smu[n]) return smu[n];//这里是map记忆化
ll ans=1;//f*g的前缀和
for(int l=2,r;r<inf && l<=n;l=r+1)//数论分块
{//这道题要卡 inf,因为可能加爆
r=n/(n/l);
ans-=(r-l+1)*get_mu(n/l);//I的求和是r-l+1,然后递归
}
return smu[n]=ans;//得到答案
}
(varphi) 的前缀和
考虑到欧拉反演的柿子：(varphi*I=id) ，令 (f=varphi,g=I,f*g=id)
(id) 的前缀和特别好算，就是：(frac{n(n+1)}{2})
ull get_ph(int n)
{
if(n<=N) return phi[n];//这里是预处理的phi
if(sph[n]) return sph[n];//map记忆化
ull ans=(ull)n*(n+1ll)/2;//要开ull
for(int l=2,r;r<inf && l<=n;l=r+1)//数论分块
{
r=n/(n/l);
ans-=(r-l+1)*get_ph(n/l);//I的求和是r-l+1,然后递归
}
return sph[n]=ans;//得到答案
}
扩展：(varphicdot id) 的前缀和
需要说明一下：(varphicdot id=sum_{i=1}^nvarphi(i)i)
令 (f=varphicdot id) ，(g=id) ，(f*g=(varphicdot i)*i) ，我们来看这个东西的前缀和好不好算：
最后一步是欧拉反演，所以他的前缀和是 (frac{n(n+1)(2n+1)}{6})
现在做一个小总结吧，杜教筛的关键是找辅助函数，让前缀和变得好算。
其他例题
这两个是一类题，都是函数结构递归，然后杜教筛处理边界：循环之美,DZY Loves Math IV