狄利克雷卷积

形式:$f*g=h$

$h(n)=\sum_{d|n}f(d)g(\frac{n}{d})$

运算法则

$(f*g)*h=f*(g*h)$

$f*g=g*f$

$f*(g+h)=f*g+f*h$

常用数论函数

设正整数$n$按照算数基本定理分解质因数为$n=p_1^{c_1}p_2^{c_2}\cdots p_m^{c_m}$,

积性函数,$(a,b)=1,f(ab)=f(a)f(b)$

$\mu(n)=\begin{cases}0 & \exists i\in[1,m],c_i>1 \\1 &m\equiv 0(\operatorname{mod}2),\forall i\in[1,m],c_i=1\\ -1 &m\equiv 1(\operatorname{mod} 2),\forall i\in[1,m],c_i=1\end{cases}$

$d(n)=m$,即约数个数

$\sigma(n)=\sum_{d|n}d=\sum_{d=1}^n[d|n]d=\prod_{i=1}^m \frac{1-{p_{i}}^{c_{i}+1}}{1-p_i}$

完全积性函数,$f(ab)=f(a)f(b)$

$\epsilon(e)(n)=[n=1]$

$I(n)=1$

$id(n)=n$

卷积运用

$\mu*I=\epsilon$

$\varphi*I=id$

小性质

$~~~~~\varphi*I*\mu=id*\mu\\\rightarrow \varphi*\epsilon=id*\mu\\\rightarrow \varphi(n)=\sum_{d|n}\mu(d)\cdot \frac{n}{d}$