狄利克雷卷积

（之前本想在莫比乌斯反演的时候一起写了，但发现这东西性质还挺多，便再开一篇……
狄利克雷卷积是莫比乌斯反演和杜教筛的理论基础。

几个函数

1. 常数函数：\(1(n)=1\)
2. 单位函数：\(\epsilon(n)=[n=1]\)
3. （约数个数）\(\tau(n)=\sum\limits_{d|n}1\)
4. （约数之和）\(\sigma(n)=\sum\limits_{d|n}d\)
5. （素因子个数）\(\omega(n)=\sum\limits_{p|n}1\)
6. \(id(n)=n\)

定义

定义两个数论函数\(f(n)\)与\(g(n)\)的 狄利克雷(Dirichlet)卷积 为\[(f*g)(n)=\sum_{d|n}f(d)g(\frac{n}{d})\]此运算满足交换律、结合律、分配率，逆元。
并规定\(\epsilon\)为狄利克雷卷积单位元（任何函数与其卷积函数不变)。

函数之间的卷积关系

\(1*\mu=\epsilon\)
\(\phi * 1=id\)
\(\phi = id * \mu\)（这个非常重要！）
\(\tau = 1 * 1\qquad 1 = \mu * \tau\)

推论

两个积性函数\(f(n),g(m)\)的狄利克雷卷积\(t(mn)\)仍为积性函数。
证明：\[\begin{aligned} t(nm)&=\sum_{d\mid nm} f(d)g\left(\frac{nm}d\right)\\&=\sum_{a\mid n,b\mid m} f(ab) g\left(\frac{nm}{ab}\right)\\&=\sum_{a\mid n,b\mid m} f(a) f(b) g\left(\frac na\right) g\left(\frac mb\right)\\&=\left(\sum_{a\mid n} f(a) g\left(\frac na\right)\right)\left(\sum_{b\mid m}f(b) g\left(\frac mb\right)\right)\\&= f(n) g(m)\end{aligned} \]QED。

狄利克雷卷积

原文：https://www.cnblogs.com/wzzyr24/p/11748594.html