狄利克雷生成函数

• 定义

  对于一个数论函数，设在 \(i\) 处的点值为 \(f_i\)，则定义它的狄利克雷生成函数DGF（Dirichlet Generating Function）为 \(F(x)=\sum\limits_{i=1}^{+\infty}\frac{f_i}{i^x}\)。

  根据定义可以知道，若一个DGF为 \(F(x)\)，则原数论函数点积 \(Id\) 的DGF为 \(F(x-1)\)。

  若存在两个狄利克雷生成函数 \(F,G\)，其乘积为（设 \(h = f *g\)）：

  \[(F\times G)(x)=\sum\limits_{i=1}^{+\infty}\frac{\sum\limits_{d|i}f(d)\times g(i/d)}{i^x}=H(x) \]

  发现两个函数的DGF的乘积恰好等于其狄利克雷卷积的DGF。

  （感觉最大的用处就是利用上面这个性质，杜教筛的时候不用凑了）。

  定义黎曼Zeta函数为 \(\zeta(x)=\sum\limits_{i=1}^{+\infty}\frac{1}{i^x}\)

• 常见函数的DGF

  1. 单位元函数的DGF显然 \(1\)

  2. 恒等函数 \(I\) 的DGF为 \(\zeta(x)\)

  3. 莫比乌斯函数 \(\mu\) 的DGF：

     \[\prod_{p\in prime}(1- \frac{1}{p^x})=\frac 1{\prod_{p\in prime}\frac 1 {1-p^{-x}}}=\frac1 {\zeta(x)} \]

  4. 仅在 \(k\) 次方处值为 \(1\) 的函数的DGF为 \(\zeta(kx)\)。

  5. 幂函数 \(Id_k\) 的DGF为：

  \[\prod_{p\in prime}\sum\limits_{i=0}^{+\infty}\frac{p^{ik}}{p^{ix}}=\prod_{p\in prime}\frac 1 {1-p^{k-x}}=\zeta(x-k) \]
  6. 欧拉函数 \(\varphi\) 的DGF为：
  \[ \prod_{p\in prime}\sum\limits_{i=0}^{+\infty} \frac {p^i-p^{i-1}}{p^{ix}}=\prod_{p\in prime}\frac{1-p^{-x}}{1-p^{1-x}}=\frac{\zeta(x-1)}{\zeta(x)} \]
  7. 定义刘维尔函数为 \(\lambda(x)=(-1)^{\Omega(x)}\)。其中 \(\Omega(x)\) 表示 \(x\) 的质因子个数（可重复）。刘维尔函数的DGF为：
     \[\prod_{p\in prime} \sum\limits_{i=0}^{+\infty}\frac{(-1)^i}{p^{ix}}=\prod_{p\in prime}\frac{1}{1+p^{-x}}=\frac{\zeta(2x)}{\zeta(x)} \]

（以上均摘自Binary_Search_Tree的博客，有删改，原文链接）

生成函数

原文：https://www.cnblogs.com/With-penguin/p/13714992.html