狄利克雷卷积

定义

狄利克雷卷积:$\displaystyle (f \times g)(n) = \sum_{d|n}f(d)*g(\frac{n}{d})$

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

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

数论函数: 如果一个函数的定义域为正整数,值域为复数,则称此函数为数论函数。常见的数论函数有欧拉函数$\varphi$和莫比乌斯函数$\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. 单位元 单位函数$\epsilon$,使得$f= \epsilon \times f =f \times \epsilon$
单位函数的取值:$n=1$$\epsilon(n)=1$$n$取其他值时$\epsilon(n)=0$。 5. 逆元 对于任意数论函数$f$,如果$f(1) \not = 0$,则存在唯一的逆函数$f^{-1}$,使得 $f \times f^{-1} = \epsilon$
对于$n=1$,有:${f^{-1}(1)={\frac {1}{f(1)}}}$
对于$n>1$,有:$ {f^{-1}(n)={\frac {-1}{f(1)}}\displaystyle \sum _{d|n,n\neq d}f({\frac {n}{d}})f^{-1}(d)}$

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

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

特殊函数

由于$\displaystyle \sum_{d|n}\varphi(d) = n$易得:
$\varphi \times 1 = n$
回顾莫比乌斯反演:
$\displaystyle F(n)=\sum_{d|n}f(d)$
这句话的意思就是$f \times 1 = F$

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

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

根据狄利克雷卷积的交换律,上面的式子可以改写:
$f = F \times \mu$

$\displaystyle f(n)=\sum_{d|n}\mu (\frac{n}{d})F(d)$

莫比乌斯反演另有一种用途广泛的形式:
$\displaystyle F(n) = \sum_{n|d} f(d)$,则有$\displaystyle f(n) = \sum_{n|d}\mu(\frac{d}{n})F(d)$.

积性函数

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

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

两个例子:欧拉函数$\varphi$和莫比乌斯函数$\mu$

都可以用线性筛求。

快速求因子

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

做法:先跑一遍线性筛,以$son[i]$记录把$i$筛掉的最小的质数。

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

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

积性函数前缀和

orz杜教筛。留坑待补。


Update on 2016.8.30

此坑已补。


CC0协议 @ ruanxingzhi 2017. CC0是啥玩意?
Home apps close