狄利克雷卷积
引入1：积性函数
- 定义数论函数为定义域是正整数，而值域是复数的函数。
- 定义积性函数为满足如果$a$, $b$ 互质则$f(ab) = f(a)f(b)$ 的数论函数。
- 定义完全积性函数为对于任意$a$, $b$ 都有$f(ab) = f(a)f(b)$ 的数论函数。
- 对于一个积性函数，对任意 $n= \prod a_i^{k_i} $ ，只要知道$f(a_i^{k_i})$就能确定$n$.
- 对于完全积性函数，我们只要知道所有的$f(p_i)$ 就够了。
- 单位函数：$\varepsilon(n)=[n=1]$。（完全积性）
- 恒等函数：$\operatorname{id}k(n)=n^k$，$\operatorname{id}{1}(n)$ 通常简记作 $\operatorname{id}(n)$。（完全积性）
- 常数函数：$1(n)=1$。（完全积性）
- 除数函数：$\sigma_{k}(n)=\sum_{d\mid n}d^{k}$。$\sigma_{0}(n)$ 通常简记作 $d(n)$ 或 $\tau(n)$，$\sigma_{1}(n)$ 通常简记作 $\sigma(n)$。
- 欧拉函数：$\varphi(n)=\sum_{i=1}^n[\gcd(i,n)=1]$
- 莫比乌斯函数：$\mu(n)=\begin{cases}1&n=1\0&\exists d>1,d^{2}\mid n\(-1)^{\omega(n)}&\text{otherwise}\end{cases}$，其中 $\omega(n)$ 表示 $n$ 的本质不同质因子个数，它是一个加性函数。
以上内容来自OI-Wiki
狄利克雷卷积
定义两个数论函数$f(n),g(n)$的卷积$h(n)$为：$h(n)=\sum_{d|n}f(d)g(\frac{n}{d})$(这其实就是狄利克雷卷积),记作$h=f * g$则有：
- $\varepsilon * f = f$
- $1 * 1 = d$
- $1 * id = \sigma$
- $1 * \varphi = id$
- $1 * \mu =\varepsilon$
性质
交换律： $fg=gf$。
结合律：$(fg)h=f(gh)$。
分配律：$(f+g)h=fh+g*h$。
等式的性质： $f=g$ 的充要条件是 $fh=gh$，其中数论函数 $h(x)$ 要满足 $h(1)\ne 0$。