数论函数：定义域在正整数的函数，更一般的说可以是定义在整数上的。
性质
\[1.(f+g)(x)=f(x)+g(x) \2.(nf)(x)=n*f(x) \]
现在设有数论函数h,g,f
若
\[ h(N)=\sum_{d \backslash N} f(d)g(\frac{N}{d})
\]
那么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\)
\[\varepsilon(x) = [x=1]
\]
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=?\)
定义
\[g(n)=\frac{1}{f(1)}([n=1]-\sum_{i \mid n, i \neq 1} f(i) g(\frac{n}{i}) \ \ )
\]
\[\begin{aligned}
& \sum_{i \mid n} f(i) g(\frac{n}{i}) \=& f(1) g(n)+\sum_{i \backslash n, i \neq 1} f(i) g(\frac{n}{i}) \=&[n=1]
\end{aligned}
\]
应用:见莫反证明咯