狄利克雷生成函数

定义

对于一个数论函数，设在\(i\)处的点值为\(a_i\)，则定义它的狄利克雷生成函数DGF（Dirichlet Generating Function）为\(f(s)=\sum\limits_{n=1}^{+\infty}\frac{a_n}{n^s}\)。
若存在两个狄利克雷生成函数\(f,g\)，其乘积为
\(fg=\sum\limits_{n=1}^{+\infty}\frac{\sum\limits_{d\vert n}f_dg_{\frac{n}{d}}}{n^s}\)。
可以发现两个DGF的乘积恰好为它们的狄利克雷卷积的DGF。
黎曼函数定义为\(\zeta(s)=\sum\limits_{n=1}^{+\infty}\frac{1}{n^s}\)
单位元函数\(e\)的DGF显然为\(e=1\)。

一些常见数论函数的DGF

恒等函数\(I\)的DGF为\(I=\sum\limits_{i=1}^{+\infty}\frac{1}{n^s}=\prod\limits_{p\in prime}\sum\limits_{i=0}^{+\infty}\frac{1}{p^{is}}=\prod\limits_{p\in prime}\frac{1}{1-p^{-s}}=\zeta(s)\)
莫比乌斯函数\(\mu\)的DGF为\(\mu=\prod\limits_{p\in prime}(1-\frac{1}{p^s})=\frac{1}{\prod\limits_{p\in prime}\frac{1}{1-p^{-s}}}=\frac{1}{\zeta (s)}\)
欧拉函数\(\varphi\)的DGF为\(\varphi=\prod\limits_{p\in prime}(1+\sum\limits_{i=1}^{+\infty}\frac{p^i-p^{i-1}}{p^{is}})=\prod\limits_{p\in prime}\frac{1-p^{-s}}{1-p^{1-s}}=\frac{\zeta(s-1)}{\zeta(s)}\)
幂函数\(Id^k\)的DGF为\(Id^k=\prod\limits_{p\in prime}\sum\limits_{i=0}^{+\infty}\frac{p^{ik}}{p^{is}}=\prod\limits_{p\in prime}\frac{1}{1-p^{k-s}}=\zeta(s-k)\)
除数函数\(\sigma\)的DGF为\(\sigma^k=Id^k\times I=\zeta(s)\zeta(s-k)\)
\(\sum\limits_{i\vert n}\mu(i)i\)的DGF为\(\prod\limits_{p\in prime}(1+\sum\limits_{i=1}^{+\infty}\frac{1-p}{p^{is}})=\prod\limits_{p\in prime}\frac{1-p^{1-s}}{1-p^{-s}}=\frac{\zeta(s)}{\zeta(s-1)}\)
从这些式子可以轻松得到它们之间的一些关系。

DGF的除法

\(F=H/G\to \sum\limits_{d\vert n}F_dG_{\frac{n}{d}}=H_n\to F_n=H_n-\sum\limits_{d\vert n,d\neq 1}F_{\frac{n}{d}}G_d\)
可以在\(O(n\log n)\)的时间内解决。

DGF的对数

\(B=\ln A\to B‘=\int \frac{A‘}{A}\)
所以只要求出导数和积分即可。
但因为整数的\(\ln\)在模意义下没有定义，所以我们用质因子个数（相同的算多个）代替。
可以在\(O(n\log n)\)时间内解决。

DGF的指数

\(B=\exp A\to B‘=A‘B\)
类似于对数，也可以在\(O(n\log n)\)时间内解决。

狄利克雷生成函数

原文：https://www.cnblogs.com/bestlxm/p/13096595.html