0.更新
upd 2023.5.18 更新了狄利克雷卷积新的一个性质，更新了常用结论的证明
1.正文
这玩意儿是这么说的：
定义一个运算：$ * $ 为狄利克雷卷积。
他是干啥的呢？把两个数论函数进行一个运算。
\[h(n)=(f * g)(n)=\sum_{d|n}f(d)g(\frac{n}{d}) \]当 \(f,g\) 都是积性函数时，他们的狄利克雷卷积 \(h\) 也是一个积性函数。
下面简单证明一下：
此处，\(n\) 不为质数。
我们设 \(n=ab\) ，其中 \(1 <a,b<n \ ,gcd(a,b)=1\)。
则有：
\[(f * g)(a)= \sum_{d_1|a}f(d_1)g(\frac{a}{d_1}) \]\[(f * g)(b)= \sum_{d_2|a}f(d_2)g(\frac{b}{d_2}) \]\[(f * g)(ab)= \sum_{d|ab}f(d)g(\frac{ab}{d}) \]\[(f * g)(a) \times (f * g)(b)= \sum_{d_1|a}f(d_1)g(\frac{a}{d_1}) \times \sum_{d_2|b}f(d_2)g(\frac{b}{d_2}) \]\[=\sum_{d_1|a,d_2|b}f(d_1)g(\frac{a}{d_1})f(d_2)g(\frac{b}{d_2}) \]\[=\sum_{d_1|a,d_2|b}f(d_1d_2)g(\frac{ab}{d_1d_2}) \]因为 \(a,b\) 互质，所以 \(d_1,d_2\) 互质。
\[=\sum_{d|n}f(d)g(\frac{n}{d}) \]证毕。
接下来是关于运算律的知识
这个运算是满足交换律、结合律的，爆算即可
还有一个性质：当函数 \(A\) 为积性函数时，有：
\[(f\cdot A)*(g\cdot A)=h\cdot A \]证明一下：
\[\sum_{d|n}(f(d)A(d))\times(g(\frac{n}{d})A(\frac{n}{d}))=A(n)\sum_{d|n}f(d)g(\frac{n}{d})=A(n)h(n) \]证毕
还有一些常用的结论需要记忆：
\(id(n)=n\)
\(\varepsilon(n)=[n==1]\)
\(I(n)=1\)
则有以下结论：
\[\mu * I = \varepsilon \]\[\mu * id=\varphi \]\[\varphi * I=id \]第一个的证明：
当 \(n=1\) 当，结论显然成立
当 \(n\not =1\) 时，考虑 \(n=\prod\limits_{i=1}^k p_i^{\alpha_i}\)
考虑哪些 \(n\) 的因数有贡献，只有所有质因子都小于 2 的才有
也就意味着有用的质因子次数必定都为 1 或 0
考虑计算答案，有奇数个质因子为 1，则 \(\mu =-1\)，否则为 1
\[\sum_{i=0}^{k} (-1)^kC_k^i=(1-1)^k=0 \]证毕
第二个的证明：
柿子为 \(\displaystyle\sum_{d|n}\mu(d)\frac{n}{d}\)
\[=\sum_{i=1}^n\sum_{d|(i,n)}\mu(d) \]\[=\sum_{i=1}^n[(i,n)=1] \]这符合 \(\varphi\) 的定义，所以成立
第三个的证明：
这个我们暴力一点来证明，假设 \(n=\prod\limits_{i=1}^{k} p_i^{\alpha_i}\)
那么我们要求的 \(\displaystyle\sum_{d|n} \varphi(d)\) 就可以化为这样的一个东西：
\[\sum_{a_1=0}^{\alpha_1}\sum_{a_2=0}^{\alpha_2}\cdots\sum_{a_k=0}^{\alpha_k} \varphi(\prod\limits_{i=1}^n p_i^{a_i}) \]我们成功化简为繁，将这个柿子从一重和式变成了无数重
其实变得更简单了，我们可以利用 \(\varphi\) 是积性函数的特性来将其拆开，变为这样：
\[(\sum_{a_1=0}^{\alpha_1}\varphi(p_1^{a_1}))\cdots(\sum_{a_k=0}^{\alpha_k}\varphi(p_k^{a_k})) \]对每一项单独求，你会发现对于第 \(i\) 项，结果为 \(p_i^{\alpha_i}\)
由此证毕
之后在一些特殊题目和杜教筛中会使用这些东西。
标签：ab,frac,狄利克,卷积,sum,varphi,mu,笔记,alpha From： https://www.cnblogs.com/LUlululu1616/p/18256423