狄利克雷卷积是函数与函数之间的运算
运算定义为：$(f*g)(x) = sum_{d|x}{f(d) * g(frac{x}{d})}$
该运算有交换律：$f*g=g*f$
有结合律：$f*(g*h)=(f*g)*h$
有分配率：$f*(g+h)=f*g+f*h$
在这种新定义的运算中有许多特殊的元素
$e$ 满足 $e(n) = [n==1]$ 即当只有$n=1$时$e(n)=1$，否则为$0$
(对命题$P$，引入符号$[P]$，如果命题成立则值为$1$，否则为$0$.)
$d$ 满足$d(n) = sum_{i<=n} [i|n]$
$sigma$ 满足$sigma(n) = sum_{i|n}{i}$
$varphi$ 满足$varphi(n) = sum_{i<=n} [gcd(i,n) == 1]$
$mu$ 满足$mu(n) = left{egin{matrix} 1 & n == 1 \ (-1)^k & a1 = a2 = …… = ak\ 0 & otherwise end{matrix} ight.$ 其中 $n = p1^{a1}*p2^{a2}*……*pk^{ak}$
$I$ 满足$I(n) = 1$
$id$ 满足$id(n) = n$
以上函数均为积性函数，(也易证)
函数简单运算
1.$e$为元，有$e*f=f$
解释：$e*f = sum_{d|n}e(d)f(frac{n}{d})$，当且仅当$d = 1$时$e(d) = 1$，此时$e(d)f(frac{n}{d}) = e(1)f(n) = f(n)$，当$d!=1$时$e(d)=0$，所以$e*f = f$
2.$mu*I = e$
解释：$mu * I = sum_{d|n}{mu(n)I(frac{n}{d})} = sum_{d|n}{mu(n)}$，又由$mu(n)$为积性函数，当$n!=1$时
$sum_{d|n}{mu(n)} = (1+mu(p1)+mu(p1^2)+……+mu(p1^{a1}))(……)(1+mu(pk)+……+mu(pk^{ak}))$，又由定义$mu(p^i)=0 (i>=2)$，$mu(p)=1 (p为质数)$
$ herefore sum_{d|n}{mu(n)} = (1+mu(p1))(……)(1+mu(pk)) = (1-1)(……)(1-1) = 0$
只有当$n == 1$时$mu(n) = 1$，所以$mu*I = e$
3.$varphi*i = id$
解释：$varphi*I = sum_{d|n}varphi(d)I(frac{n}{d}) = sum_{d|n}varphi(d)$
$=(1+varphi(p1)+varphi(p1^2)+……+varphi(p1^{a1}))(……)(1+varphi(pk)+……+varphi(pk^{ak}))$
而 $1+varphi(p)+varphi(p^2)+……+varphi(p^a) = 1+p-1+p^2-p+p^3-p^2+……+p^a-p^{a-1} = p^a$
$ herefore 原式=p1^{a1}p2^{a2}……pk^{ak} = n = id(n)$
4.$I*I = d$
解释：$I*I = sum_{d|n}I(d)I(frac{n}{d}) = sum_{d|n}1 = d(n)$
5.$mu*id = varphi$
解释：$mu*id = sum_{d|n}{mu(d)id(frac{n}{d})} = nsum_{d|n}{frac{mu(d)}{d}}$
$= n(1+frac{mu(p1)}{p1}+……+frac{mu(p1^{a1})}{p1^{a1}})(……)(1+frac{mu(pk)}{pk}+……+frac{pk^{ak}}{pk^{ak}})$
又由定义$mu(p^i)=0 (i>=2)$，$mu(p)=1 (p为质数)$
$ herefore 原式=n(1-frac{1}{p1})(1-frac{1}{p2})(……)(1-frac{1}{pk}) = varphi(n)$
6.$I*id = sigma$
解释：$I*id = sum_{d|n}{id(d)I(frac{n}{d})} = sum_{d|n}{d} = sigma(n)$
函数乘法一览表
$egin{matrix}
* & e(n) & d(n) & sigma(n) & varphi(n) & mu(n) & I(n) & id(n) \
e(n) & e(n) & d(n) & sigma(n) & varphi(n) & mu(n) & I(n) & id(n) \
d(n) & d(n) & - & - & sigma(n) & - & - & - \
sigma(n) & sigma(n) & - & - & - & - & - & - \
varphi(n) & varphi(n) & sigma(n) & - & - & - & id(n) & - \
mu(n) & mu(n) & - & - & - & - & e(n) & varphi(n) \
I(n) & I(n) & - & - & id(n) & e(n) & d(n) & sigma(n) \
id(n) & id(n) & - & - & - & varphi(n) & sigma(n) & nd(n) \
end{matrix}$
莫比乌斯反演
若$g(n) = sum_{d|n}f(d)$，则$f(n) = sum_{d|n}{g(d)mu(frac{n}{d})}$
解释：由上$g=f*I$，则$g*mu=f*I*mu$，又$mu*I=e，e*f=f$，所以$f=g*mu=sum_{d|n}{g(d)mu(frac{n}{d})}$
若$g(n) = sum_{n|d}^{d<=MAX} {f(d)}$，则$f(n) = sum_{n|d}^{d<=MAX} {g(d)mu(frac{d}{n})}$
解释：令$frac{d}{n} = k$，则$sum_{n|d}^{d<=MAX} {g(d)mu(frac{d}{n})} = sum_{k}^{nk<=MAX} {g(nk)mu(k)}$
$=sum_{k}^{nk<=MAX} {mu(k)sum_{nk|t}^{t<=MAX} {f(t)}}$
$=sum_{t}^{t<=MAX} {f(t)sum_{nk|t}{mu(k)}}$
又$sum_{nk|t}{mu(k)} = sum_{k|frac{t}{n}}{mu(k)} = mu(frac{t}{n})I(frac{t}{n}) = e(frac{t}{n})$
$ herefore sum_{t}^{t<=MAX} {f(t)sum_{nk|t}{mu(k)}} = sum_{t}^{t<=MAX} {f(t)e{(frac{t}{n})}}$
当且仅当$t = n$时$e != 0$，对求和有贡献
$ herefore sum_{t}^{t<=MAX} {f(t)e{(frac{t}{n})}}= f(n)$