狄利克雷卷积

定义

狄利克雷卷积：$(f\times g)\left(n\right)=\sum _{d|n}f\left(d\right)\ast g\left(\frac{n}{d}\right)$

一个例子：$f\left(x\right)=2x,g\left(x\right)=3x$
则$(f\times g)\left(6\right)=f\left(1\right)g\left(6\right)+f\left(2\right)g\left(3\right)+f\left(3\right)g\left(2\right)+f\left(6\right)g\left(1\right)$。
往往省略掉$n$。

狄利克雷卷积定义在数论函数上。

数论函数： 如果一个函数的定义域为正整数，值域为复数，则称此函数为数论函数。常见的数论函数有欧拉函数$\phi$和莫比乌斯函数$\mu$。

运算律： 1. 结合律 $(f\times g)\times h=f\times (g\times h)$。
2. 交换律 $f\times g=g\times f$。
3. 加法-狄利克雷卷积分配律 $f\times (g+h)=f\times g+f\times h$。
4. 单位元 单位函数$ϵ$，使得$f=ϵ\times f=f\times ϵ$。
单位函数的取值：$n=1$时$ϵ\left(n\right)=1$，$n$取其他值时$ϵ\left(n\right)=0$。 5. 逆元 对于任意数论函数$f$，如果$f\left(1\right)\ne 0$，则存在唯一的逆函数$f^{-1}$，使得 $f\times f^{-1}=ϵ$：
对于$n=1$，有：$f^{-1}\left(1\right)=\frac{1}{f\left(1\right)}$
对于$n>1$，有：$f^{-1}\left(n\right)=\frac{-1}{f\left(1\right)}\sum _{d|n,n\ne d}f\left(\frac{n}{d}\right)f^{-1}\left(d\right)$

狄利克雷卷积是对数论函数的二元运算，产生的结果也显然是一个数论函数，因此满足封闭性。又综合1、4、5，得到：

$G(数论函数,\times )$是一个群。

特殊函数

由于$\sum _{d|n}\phi \left(d\right)=n$易得：
$\phi \times 1=n$
回顾莫比乌斯反演：
$F\left(n\right)=\sum _{d|n}f\left(d\right)$
这句话的意思就是$f\times 1=F$。

根据莫比乌斯函数的性质或定义：
$\mu \times 1=ϵ$
$f\times 1=F\times ϵ=F\times \mu \times 1$。
故：$f=F\times \mu$

可以推出莫比乌斯反演定理： $f=\mu \times F$
也即日常所见的式子：
$f\left(n\right)=\sum _{d|n}F\left(\frac{n}{d}\right)\mu \left(d\right)$。

根据狄利克雷卷积的交换律，上面的式子可以改写：
$f=F\times \mu$
故
$f\left(n\right)=\sum _{d|n}\mu \left(\frac{n}{d}\right)F\left(d\right)$。

莫比乌斯反演另有一种用途广泛的形式：
若$F\left(n\right)=\sum _{n|d}f\left(d\right)$，则有$f\left(n\right)=\sum _{n|d}\mu \left(\frac{d}{n}\right)F\left(d\right)$.

积性函数

数论函数$f$，如果对于所有$a\perp b$有$f(a\ast b)=f\left(a\right)\ast f\left(b\right)$，则称$f$为积性函数。
进一步，如果对于所有$a,b\in Z_{+}$都有$f(a\ast b)=f\left(a\right)\ast f\left(b\right)$，则称$f$为完全积性函数。

两个积性函数的狄利克雷卷积也是积性函数。

两个例子：欧拉函数$\phi$和莫比乌斯函数$\mu$。

都可以用线性筛求。

快速求因子

可以以$O\left(n\right)$的代价预处理$[1,n]$的所有数，然后$O\left(\log n\right)$分解质因子。

做法：先跑一遍线性筛，以$son\left[i\right]$记录把$i$筛掉的最小的质数。

分解质因数的时候，不停地n=n/son[n]来分解。

可以证明复杂度是单次$O\left(\log n\right)$：每迭代一次，$n$被除以$son\left[n\right]$，而$son\left[n\right]$最小为$2$，故时间复杂度不超过$O\left(\log n\right)$。

积性函数前缀和

orz杜教筛。留坑待补。

---

Update on 2016.8.30

此坑已补。