对于两个数论函数\(f\)和\(g\)，定义\((f*g)(n)=\sum_{d|n}f(d)\cdot g(\frac{n}{d})\)
并且我们可以发现，狄利克雷卷积是满足交换律，结合律以及分配律的。
你或许还需要知道一些完全积性函数：
1、\(I(n)\)不变的函数，定义为\(I(n)=1\)
2、\(id(n)\)单位函数，定义为\(id(n)=n\)
3、\(ε(n)\)定义为：\(ε(n)=[n==1]\)。为狄利克雷卷积的乘法单位。
这些函数在接下来将很有用
很显然，是不是有\(\mu*I=ε\)
那么接下来我们来证明莫比乌斯反演吧：
\[
F(n)=\sum_{d|n}f(d)
\]
那么有
\[
F=f*I
\]
想到\(\mu*I=ε\)，考虑在等式两边卷上一个$\mu $
\[
F*\mu=f*I*\mu\F*\mu=f*ε
\]
然而\(f*ε=f\)（可以自己想想）
然后就得出了
\[
f(n)=\sum_{d|n}F(\frac{n}{d})\mu(d)
\]
如果定义
\[
F(n)=\sum_{n|d}f(d)
\]
就可以得出莫比乌斯反演的另一种形式
\[
f(n)=\sum_{n|d}\mu(\frac{d}{n})F(d)
\]
杜教筛是一种可以快速求出积性函数前缀和的算法
假设我们现在需要求\(\sum_{i=1}^{n}h[i]\)
而\(n\)高达\(10^9\)，线性筛就做不了了
我们设\(f,g\)，并且\(f*h=g\)
那么我们设\(S[n]=\sum_{i=1}^{n}h[i]\)
\[
\sum_{i=1}^{n}g(i)=\sum_{i=1}^{n}\sum_{d|i}f(d)h(\frac{i}{d})\\sum_{i=1}^{n}g(i)=\sum_{d=1}^{n}f(d)\sum_{i=1}^{\lfloor\frac{n}{d} \rfloor}h(i)\\sum_{i=1}^{n}g(i)=\sum_{d=1}^{n}f(d)h(\lfloor\frac{n}{d} \rfloor)\S(n)f(1)=\sum_{i=1}^{n}g(i)-\sum_{d=2}^{n}f(d)S(\lfloor\frac{n}{d} \rfloor)\S(n)=\frac{\sum_{i=1}^{n}g(i)-\sum_{d=2}^{n}f(d)S(\lfloor\frac{n}{d} \rfloor)}{f(1)}\\]
\(f(1)\)很容易知道，对于右边里的\(S(\lfloor \frac{n}{d}\rfloor)\)递归求解就好了
但是\(g,f\)的选择不是固定的，需要凭经验选取
由于博主才疏学浅，可能讲的有些不清楚，会后续更改补充
原文：https://www.cnblogs.com/lcxer/p/10551641.html