Dirichlet（狄利克雷）卷积

数论函数：定义域在正整数的函数，更一般的说可以是定义在整数上的。

性质

现在设有数论函数h,g,f
若

那么h就被称f和d的狄利克雷卷积，可以记作h=f*g ，这里的乘号是卷积乘.
eg.\(h(6)=f(1)g(6)+f(2)g(3)+f(3)g(2)+f(6)g(1)\)

性质:
1.
定义单位函数\(\varepsilon\)为狄利克雷卷积的单位元，对于任意函数f，都\(f*\varepsilon=\varepsilon*f=f\)

3.狄利克雷卷积满足\(结合律f*(g*t)=(f*g)*t,交换律f*g=g*f,分配律f*(t+g)=f*t+f*g\)

4.如果f和g都是积性函数，那么它们的狄利克雷卷积也是积性函数,那么就可以用欧拉筛来筛狄利克雷卷积，其实还有其他作用.
5.有逆元

计算狄利克雷卷积

计算h(N)需要枚举N的约数。时间复杂度\(O(\sqrt N)\)
求前N项的h(x)，时间复杂度为\(O(N \ log \ N)\)

求狄利克雷卷积的逆元
狄利克雷卷积有一个性质：对每个\(f(1)≠0\)的函数f，都存在一个函数g使得 \(f?g=?\)
定义

应用:见莫反证明咯

Dirichlet（狄利克雷）卷积

原文：https://www.cnblogs.com/QQ2519/p/15140529.html