狄利克雷生成函数 学习笔记
热言热语
·
·
个人记录
基础知识
定义
狄利克雷生成函数
对于无穷数列 \{a_n\}（其中 n \in \mathbb N^*），它的狄利克雷生成函数（Dirichlet Generating Function，简称 DGF）定义为
f(s) = \sum_{n=1}^\infty {a_n \over n^s}
= {a_1 \over 1^s} + {a_2 \over 2^s} + {a_3 \over 3^s} + \cdots
这和传统的生成函数的形式（形式幂级数）有所不同。
一个数论函数的 DGF 即为它取值对应的数列的 DGF。
贝尔级数
对于数论函数 f(n) 和质数 p，f 模 p 的贝尔级数（Bell series）定义为
f_p(x) = \sum_{n=0}^\infty f(p^n)x^n
它和狄利克雷生成函数之间有密切的联系。
积性函数的 DGF 和贝尔级数
设 f(n) 是一个积性函数，由积性函数的性质可知若 n = \prod p_i^{k_i}，则 f(n) = \prod f(p_i^{k_i})。
那么，f(n) 的 DGF 可以表示为
\begin{aligned}
F(s) &= \sum_{n=1}^\infty {f(n) \over n^s} \\
&= \sum_{\forall p \in \mathbb P, k_p \ge 0} \prod_{p \in \mathbb P} {f(p^{k_p}) \over p^{k_ps}} \\
&= \prod_{p \in \mathbb P} \sum_{k \ge 0} {f(p^k) \over p^{ks}} \\
&= \prod_{p \in \mathbb P} \left(1+{f(p) \over p^s}+{f(p^2) \over p^{2s}}+\cdots\right)
\end{aligned}
其中 \mathbb P 代表全体质数集。
此外，f 模质数 p 的贝尔级数由其定义式给出，并且 f(n) 可以由 f 模全体质数的贝尔级数唯一确定。
DGF 与贝尔级数的关系
对于积性函数 f(n)，由上式可以发现，它的 DGF F(s) 可表示为 f 模 p 的贝尔级数 f_p 卷积的形式，即
F(s) = \prod_{p \in \mathbb P} f_p(p^{-s})
完全积性函数的情况
若 f(n) 是一个完全积性函数，容易验证对于任意质数 p 和正整数 k，有 f(1)=1 且 f(p^k) = f(p)^k。
那么，f(n) 的 DGF 就可以表示为（下式规定 0^0=1）
\begin{aligned}
F(s) &= \prod_{p \in \mathbb P} \sum_{k=0} {f(p)^k \over p^{ks}} \\
&= \prod_{p \in \mathbb P} \sum_{k=0} \left(f(p) \over p^s\right)^k \\
&= \prod_{p \in \mathbb P} {1 \over 1 - \dfrac{f(p)}{p^s}}
\end{aligned}
$$
f_p(x) = \sum_{k=0}^\infty f(p)^kx^k = {1 \over 1-f(p)x}
$$
## 运算
### 加减
由于 DGF 和贝尔级数多用于积性函数相关的推导，一般这没有实际意义。
### 卷积
#### DGF
设两个数列 $\{a_n\}$ 和 $\{b_n\}$ 对应的 DGF 分别为 $f(s)$ 和 $g(s)$，考察它们的卷积 $h(s)$。
$$
\begin{aligned}
h(s) &= f(s)g(s) \\
&= \sum_{p=1}^\infty {a_p \over p^s} \sum_{q=1}^\infty {b_q \over q^s} \\
&= \sum_{p=1}^\infty \sum_{q=1}^\infty {a_p b_q \over (pq)^s} \\
&= \sum_{n=1}^\infty \sum_{pq=n} {a_p b_q \over n^s} \\
&= \sum_{n=1}^\infty {\displaystyle \sum_{d|n} a_d b_{n \over d} \over n^s}
\end{aligned}
$$
容易发现，$h(s)$ 就是数列 $\{a_n\}$ 和 $\{b_n\}$ 的狄利克雷卷积对应的 DGF。
下文中会用 $f \ast g$ 表示两个数论函数 $f(n)$ 和 $g(n)$ 的狄利克雷卷积。
#### 贝尔级数
设 $f(n)$ 和 $g(n)$ 均为积性函数，容易验证对于任意质数 $p$ 和自然数 $k$ 有
$$
\begin{aligned}
(f \ast g)(p^k) &= \sum_{d|p^k} f(d)g\left(p^k \over d\right) \\
&= \sum_{i=0}^k f(p^i)g(p^{k-i}) \\
&= \sum_{i=0}^k ([x^i]f_p)([x^{k-i}]g_p) \\
&= [x^k] f_pg_p
\end{aligned}
$$
也就是
$$
(f \ast g)_p(x) = f_p(x) g_p(x)
$$
### 平移
设 $f(n)$ 为数论函数，且 $f(n)$ 的 DGF 为 $F(s)$，$f$ 模 $p$ 的贝尔级数为 $f_p(x)$，则
$$
F(s-k) = \sum_{n=1}^\infty {f(n) \over n^{s-k}} = \sum_{n=1}^\infty {n^kf(n) \over n^s}
$$
这也是一个 DGF，它对应的数论函数为 $f'(n) = n^kf(n)$。
可以发现，这相当于 $f(n)$ 点积一个完全积性函数 $\mathrm{id}_k$，并且如果 $f(n)$ 为积性函数，则平移后的 $f'(n)$ 也是积性函数。
考虑 DGF 平移后对应贝尔级数的变化：
$$
f'_p(x) = \sum_{i=0}^\infty f'(p^i)x^i = \sum_{i=0}^\infty f(p^i)p^{ki}x^i = f_p(p^kx)
$$
### 乘法逆
这里我们只讨论积性函数对应的 DGF 和贝尔级数的乘法逆。
设 $f(n)$ 为积性函数，且 $f(n)$ 的 DGF 为 $F(s)$，$f$ 模 $p$ 的贝尔级数为 $f_p(x)$。
根据形式幂级数的知识，$f_p$ 存在乘法逆且乘法逆常数项为 $1$，设它的乘法逆为 $f_p^{-1}$，则
$$
{1 \over F(s)} = \prod_{p \in \mathbb P} f_p^{-1}(p^{-s})
$$
这也是一个 DGF，并且它对应了一个积性函数，可以看作 $f(n)$ 在狄利克雷卷积下的逆元。
#### 完全积性函数的情况
若 $f(n)$ 具有完全积性，则
$$
{1 \over F(s)} = \prod_{p \in \mathbb P} \left(1 - {f(p) \over p^s}\right)
$$
它对应的数论函数 $f^{-1}(n) = f(n)\mu(n)$。
### 导数
设 $f(n)$ 为积性函数，根据求导法则，它的 DGF $F(s)$ 的导数为
$$
F'(s) = \sum_{n=1}^\infty -{f(n) \ln n \over n^s}
$$
然而这一般没有什么用，因为 $\ln n$ 太丑了，没人想要它。
有时在具体的题目中，可以用可重因数个数来代替对数，来完成一些类似多项式对数和指数函数的神秘操作。（先咕着）
## 应用
### 常见数论函数的 DGF 和贝尔级数
下面讨论一些常见数论函数（所对应数列）的 DGF 和贝尔级数。
为叙述方便，统一记所讨论的数论函数为 $f(n)$，对应的数列为 $a_n$，它的 DGF 为 $F(s)$，模质数 $p$ 的贝尔级数为 $f_p(x)$。
#### 1. 幺元函数
首先是最简单的情况：$a_n = \epsilon(n) = [n=1]$。
显然，它的 DGF 为 $F(s) = 1$，模 $p$ 的贝尔级数为 $f_p(x) = 1$。
#### 2. 恒等函数
即 $a_n = I(n) = 1$，它的 DGF 为
$$
F(s) = \sum_{n=1}^\infty {1 \over n^s}
= {1 \over 1^s} + {1 \over 2^s} + {1 \over 3^s} + \cdots
$$
不难发现这就是黎曼 zeta 函数 $\zeta(s)$。
同时，它模质数 $p$ 的贝尔级数为
$$
f_p(x) = \sum_{k=0}^\infty x^k = {1 \over 1-x}
$$
#### 3. 单位函数
即 $a_n = \mathrm{id}(n) = n$，它的 DGF 为
$$
F(s) = \sum_{n=1}^\infty {n \over n^s} = \sum_{n=1}^\infty {1 \over n^{s-1}} = \zeta(s-1)
$$
同时
$$
f_p(x) = \sum_{k=0}^\infty p^kx^k = {1 \over 1-px}
$$
类似地，$k$ 次标号函数 $\mathrm{id}_k(n) = n^k$ 的 DGF 为 $F(s) = \zeta(s-k)$，贝尔级数为 $f_p(x) = \dfrac 1{1-p^kx}$。
#### 4. 因数个数函数
即 $\displaystyle a_n = \sigma_0(n) = \sum_{d|n}$。由 $\sigma_0 = I \ast I$ 结合前面的卷积性质可知，$F(s) = \zeta^2(s)$，$f_p(x) = \dfrac 1{(1-x)^2}$。
类似地，定义 $\displaystyle \sigma_k(n) = \sum_{d|n} d^k$，则 $\sigma_k = I \ast \mathrm{id}_k$，所以 $F(s) = \zeta(s)\zeta(s-k)$，$f_p(x) = \dfrac 1{(1-x)(1-p^kx)}$。
特别地，当 $k=1$ 时，$\sigma_1(n)$ 可简记为因数和函数 $\sigma(n)$，它的 DGF 为 $F(s) = \zeta(s)\zeta(s-1)$，贝尔级数为 $f_p(x) = \dfrac 1{(1-x)(1-px)}$。
#### 5. 欧拉函数
即 $\displaystyle a_n = \varphi(n) = \sum_{d=1}^n [\gcd(n,d)=1]$。由 $\mathrm{id} = I \ast \varphi$，$F(s) = \dfrac{\zeta(s-1)}{\zeta(s)}$，$f_p(x) = \dfrac{1-x}{1-px}$。
#### 6. 莫比乌斯函数
即 $a_n = \mu(n)$，其中 $\mu$ 满足 $\epsilon = I \ast \mu$。由定义式，$F(s) = \dfrac 1{\zeta(s)}$，$f_p(x) = 1-x$。
### 莫比乌斯反演
**经典形式：** 已知 $\displaystyle f(n) = \sum_{d|n} g(d)$，求出 $g$ 关于 $f$ 的表达式。
设 $f$ 和 $g$ 的 DGF 分别为 $F(s)$ 和 $G(s)$。
由题设可得 $f = I \ast g$，所以 $F(s) = \zeta(s)G(s)$。
因此 $G(s) = \dfrac {F(s)}{\zeta(s)}$，即 $g = \mu \ast f$。
**拓展：** 已知 $f = g \ast h$，其中 $g$ 为完全积性函数，求出 $h$ 关于 $f,g$ 的表达式。
同样设 $f,g,h$ 的 DGF 分别为 $F(s)$，$G(s)$ 和 $H(s)$。
由题设可得 $F(s) = G(s)H(s)$，即 $H(s) = \dfrac{F(s)}{G(s)}$。
由完全积性函数 DGF 乘法逆的相关知识可得 $h = f \ast g^{-1}$，其中 $g^{-1}(n) = g(n)\mu(n)$。
当然，根据 DGF 乘法逆的知识，上述做法也可以推广到 $g$ 为积性函数的情况。
### 积性函数前缀和
DGF 和贝尔级数可以用比普通做法更为简洁的方式推出一些积性函数求和的式子。
#### 1. 结合杜教筛
我们现在有一个积性函数 $f(n)$，想要利用杜教筛求出它的前缀和。
众所周知，杜教筛需要找另一个数论函数 $g$，使得 $f \ast g$ 和 $g$ 在所有 $\left\lfloor\dfrac n d\right\rfloor$ 的前缀和能 $O(n^{2 \over 3})$ 求出。
而有时候这个 $g$ 并不好找，这时 DGF 和贝尔级数就能派上用场了。
下面我们设 $f(n)$ 的 DGF 为 $F(s)$，$f$ 模 $p$ 的贝尔级数为 $f_p(x)$，$g$ 同理。
##### 例 1：欧拉函数
> 求积性函数 $f(n)=\varphi(n)$ 的前缀和。
这时 $F(s) = \dfrac{\zeta(s-1)}{\zeta(s)}$，于是考虑令 $G(s) = \zeta(s)$，即 $g(n)=1$。
那么 $F(s)G(s) = \zeta(s-1)$，即 $f \ast g = \mathrm{id}$。
显然，$f \ast g$ 和 $g$ 的前缀和都能 $\Theta(1)$ 求出。
##### 例 2：莫比乌斯函数
> 求积性函数 $f(n)=\mu(n)$ 的前缀和。
这时 $F(s) = \dfrac 1{\zeta(s)}$，于是考虑令 $G(s) = \zeta(s)$，即 $g(n)=1$。
那么 $F(s)G(s) = 1$，即 $f \ast g = \epsilon$。
显然，$f \ast g$ 和 $g$ 的前缀和都能 $\Theta(1)$ 求出。
##### 例 3：[洛谷 P3768 简单的数学题](https://www.luogu.com.cn/problem/P3768)
> 求积性函数 $f(n) = n^2 \varphi(n)$ 的前缀和，对大质数取模。
由 DGF 平移的性质可知，$F(s) = \dfrac{\zeta(s-3)}{\zeta(s-2)}$，于是考虑令 $G(s) = \zeta(s-2)$，即 $g(n)=n^2$。
那么 $F(s)G(s) = \zeta(s-3)$，即 $(f \ast g)(n) = n^3$。
众所周知，
$$
\begin{aligned}
\sum_{i=1}^n i^2 &= {n(n+1)(2n+1) \over 6} \\
\sum_{i=1}^n i^3 &= {n^2(n+1)^2 \over 4}
\end{aligned}
$$
那么 $f \ast g$ 和 $g$ 的前缀和也就能 $\Theta(1)$ 求出了。
##### 例 4
> 已知积性函数 $f(n)$ 满足 $\forall p \in \mathbb P, k \in \mathbb N^*,\ f(p^k)=p^k+1$，求 $f(n)$ 的前缀和，对大质数取模。
推一波式子：
$$
\begin{aligned}
F(s) &= \prod_{p \in \mathbb P} \left(1+\sum_{k=1}^\infty {p^k+1 \over p^{ks}}\right) \\
&= \prod_{p \in \mathbb P} \left(\sum_{k=0}^\infty {p^k \over p^{ks}} + \sum_{k=1}^\infty {1 \over p^{ks}}\right) \\
&= \prod_{p \in \mathbb P} \left({1 \over 1-p^{1-s}} + {p^{-s} \over 1-p^{-s}}\right) \\
&= \prod_{p \in \mathbb P} {1-p^{1-2s} \over (1-p^{-s})(1-p^{1-s})} \\
&= {\zeta(s)\zeta(s-1) \over \zeta(2s-1)}
\end{aligned}
$$
考虑令
$$
G(s) = \zeta(2s-1) = \sum_{n=1}^\infty {1 \over n^{2s-1}} = \sum_{n=1}^\infty {n \over (n^2)^s}
$$
那么 $g(n)$ 只在 $n$ 为完全平方数时有值 $\sqrt n$，显然它的前缀和可以快速计算。
这时 $f \ast g = \sigma$，它的前缀和可以用除法分块 $\Theta(\sqrt n)$ 求出。
于是我们就可以愉快地上杜教筛了，时间复杂度 $\Theta(n^{2 \over 3})$。
然而这做法纯属想多了，因为……
__Bonus 1:__ 本题有利用后文介绍的 Powerful Number 的 $\Theta(\sqrt n \ln n)$ 做法。
__Bonus 2:__ 本题有利用莫比乌斯反演的 $\Theta(\sqrt n \ln n)$ 做法，~~留作练习~~。
~~（果然杜教筛还是没什么用啊……）~~
#### 2. 结合 Powerful Number
##### 定义
Powerful Number 就是所有质因数次数不小于 2 的数，如 1, 4, 8, 9, 16。
##### 性质
$n$ 以内的 Powerful Number 数量为 $\Theta(\sqrt n)$。
证明：下界显然，上界可以积分（总之就是咕）。
这一性质是利用 Powerful Number 求积性函数前缀和的基石。
##### 应用
我们不知道又从哪里搞到了一个积性函数 $f(n)$，然后不知道为啥又要求它的前缀和。
仿照杜教筛的套路，我们再去路边捡一个函数 $g$，让它和 $f$ 卷积。
不同的是，这次我们要找的 $g$ 满足对于任意质数 $p$，$g(p) = -f(p)$。
接下来，按照套路，我们要考察 $f \ast g$，不妨先看看 $f \ast g$ 在质数 $p$ 处的取值：
$$
(f \ast g)(p) = f(1)g(p) + g(1)f(p) = f(p)-f(p) = 0
$$
于是我们惊奇地发现，$f \ast g$ 在质数处的取值恒为 $0$。
更进一步，$f \ast g$ 也是个积性函数，所以 $(f \ast g)(n)$ 非零当且仅当 $n$ 是一个 Powerful Number。
那么这有什么用呢？
回到最开始的地方，我们要求 $f$ 的前缀和。
现在我们有了 $f \ast g$，要凑出 $f$，还需要把它和 $g$ 在狄利克雷卷积下的逆元 $h$ 卷积，即 $f = (f \ast g) \ast h$。
设 $f(n)$ 的 DGF 为 $F(s)$，$g(n)$ 的 DGF 为 $G(s)$，$\dfrac 1{G(s)}$ 对应的数论函数为 $h(m)$，这样 $h$ 即为 $g$ 在狄利克雷卷积下的逆元（反之亦然）。
对于质数 $p$，由于 $g \ast h = \epsilon$，所以 $g(1)h(p) + h(1)g(p) = 0$，即 $h(p) = -g(p) = f(p)$。
上述推导是可逆的，也就是说，只要满足了 $h(p) = f(p)$，那么对应的 $f \ast g$ 必然只在 Powerful Number 处非零，也就可以使用这种方法求出 $f$ 的前缀和。
继续推出完整的式子：
$$
\begin{aligned}
F(s) &= F(s)G(s) {1 \over G(s)} \\
&= \sum_{n=1}^\infty {(f \ast g)(n) \over n^s} \sum_{m=1}^\infty {h(m) \over m^s} \\
&= \sum_{n=1}^\infty (f \ast g)(n) \sum_{m=1}^\infty {h(m) \over (nm)^s}
\end{aligned}
$$
假设我们要求 $f(1 \ldots N)$ 的和，对于一个 Powerful Number $n$，它对答案的贡献为
$$
(f \ast g)(n) \sum_{m=1}^{\left\lfloor\frac N n\right\rfloor} h(m)
$$
一般来说 $f \ast g$ 能在常数时间内求出，如果我们找到的 $h(m)$ 的前缀和也能快速计算，那我们就成功地解决了这个问题。
##### 算法实现与复杂度分析
直接 DFS 枚举所有 $N$ 以内的 Powerful Number 并统计答案即可，枚举的复杂度与 Powerful Number 的数量同阶，即 $\Theta(\sqrt N)$。
对于 $f \ast g$，DFS 过程中就能顺便得到质因数分解和 $f \ast g$ 的函数值，大部分情况下求单点函数值是 $\Theta(1)$ 的，所以这部分复杂度也是 $\Theta(\sqrt N)$。
对于 $h$ 的前缀和，我们可以先线筛求出 $\sqrt N$ 以内的 $h(m)$，这样只有当 $n \lt \sqrt N$ 时才需要再计算一次 $h$ 的前缀和。这部分的复杂度将在稍后分析。
对于空间复杂度，只有线性筛所需的 $\Theta(\sqrt N)$。
梳理一下过程：
- __解题思路__
1. 尝试凑出一个函数 $h(m)$ 使得 $h(p)=f(p)$，并且 $h(m)$ 的前缀和可以快速计算；
2. 根据 $g \ast h = \epsilon$ 找到对应的 $g$，并求出 $f \ast g$ 在质数幂处的取值。
- __算法实现__
1. 线性筛求出 $\sqrt N$ 以内的质数和 $h(m)$ 的前缀和；
2. 从小到大枚举每个质因数的次数跑 DFS，对 $N$ 以内的每个 Powerful Number $n$ 统计贡献：
1. DFS 过程中可以根据积性顺便求出 $(f \ast g)(n)$；
2. 计算 $h(1 \ldots \left\lfloor\frac N n\right\rfloor)$ 的和：
1. 若 $n \le \sqrt N$，直接利用线筛求得的值；
2. 否则需要再计算一次 $h$ 的前缀和。
实现上，DFS 过程中可以只记录 $\left\lfloor\frac N n\right\rfloor$、$f \ast g$ 的函数值和当前枚举到的质因数这三个状态。
下面我们尝试估计一下计算 $h$ 的前缀和这部分的总复杂度 $T(N)$。
先假设计算 $h(1 \ldots n)$ 的和的复杂度为 $T_h(n)$。
由于 $\sqrt N$ 以内的 Powerful Number 数量为 $\Theta(N^{1 \over 4})$，我们可以得到 $T(N) = O\big(N^{1 \over 4}T_h(N)\big)$。
这个上界可能很松，为了方便进一步讨论，不妨设 $T_h(n) = \Theta(n^\alpha)$，其中 $0 \lt \alpha \lt 1$。
若只统计 Powerful Number 中完全平方数的贡献，我们可以得到 $T(N)$ 的一个下界
$$
T(N) \ge \sum_{n=1}^{\sqrt[4]N} T_h\left(N \over n^2\right)
$$
同时，由于 Powerful Number 都可以表示为 $a^2b^3$ 的形式，我们可以得到 $T(N)$ 的一个上界
$$
T(N) \le \sum_{a=1}^{\sqrt[4]N} \sum_{b=1}^{\sqrt[6]{N \over a^4}} T_h\left(N \over a^2b^3\right)
$$
由于推导过程涉及积分和多处分类讨论，过于繁琐，这里只给出计算结果：
当 $0 \lt \alpha \lt \dfrac 1 2$ 时，$T(N) = \Theta(N^{1+2\alpha \over 4})$；
当 $\alpha = \dfrac 1 2$ 时，$T(N) = \Theta(\sqrt N \ln N)$，因为有隐含常数 $\dfrac 1 4$，实际跑起来还是挺快的；
当 $\dfrac 1 2 \lt \alpha \lt 1$ 时，$T(N) = \Theta(N^\alpha)$。
##### 例 1（杜教筛中的例 4）
> 已知积性函数 $f(n)$ 满足 $\forall p \in \mathbb P, k \in \mathbb N^*,\ f(p^k)=p^k+1$，求 $f(n)$ 的前缀和，对大质数取模。
>
> $1 \le N \le 10^{13}
数据范围变大了，杜教筛跑路了……
对于质数 p，f(p) = p+1，那么我们可以考虑设 h(n) = \sigma(n)，即 n 的因数和，这样就满足了 h(p) = f(p)。
众所周知，\sigma(n) 的前缀和可以除法分块 O(\sqrt n) 求，这里有一个常数优化的小技巧，推导过程留作练习：
2\sum_{i=1}^{N} i \left\lfloor\frac N i\right\rfloor = \sum_{i=1}^{\sqrt N} \left\lfloor\frac N i\right\rfloor \left(\left\lfloor\frac N i\right\rfloor + 2i + 1\right) - \lfloor\sqrt N\rfloor^2 - \lfloor\sqrt N\rfloor^3
下面我们尝试写出 f \ast g 模 p 的贝尔级数（f_p(x) 可以由前面杜教筛一节中推出的 DGF 直接得出）：
\begin{aligned}
f_p(x) &= {1-px^2 \over (1-x)(1-px)} \\
h_p(x) &= {1 \over (1-x)(1-px)} \\
g_p(x) &= {1 \over h_p(x)} = (1-x)(1-px) \\
(f \ast g)_p(x) &= f_p(x) g_p(x) = 1-px^2
\end{aligned}
这几个函数的形式是如此优美，于是就可以愉快地利用 Powerful Number（准确地说，只有完全平方数）求 f 的前缀和了。根据前面的推导结果，时间复杂度为 \Theta(\sqrt N \ln N)。
事实上，前面提到的莫比乌斯反演做法推出的结果是一样的，但过程又臭又长，所以 Powerful Number 比它不知道高到哪里去了。
例 2
已知积性函数 f(n) 满足 \forall p \in \mathbb P, k \in \mathbb N^*,\ f(p^k)=p^c，求 f(n) 的前缀和，对大质数取模。
1 \le N \le 10^{13}$，$0 \le c \le 10^3
对于质数 p，f(p) = p^c，那么我们可以考虑设 h(n) = \mathrm{id}_c(n) = n^c，即满足了在质数处取值相同这一条件，并且 h(n) 的前缀和可以利用自然数幂和有关知识实现 \Theta(c^2) 预处理 \Theta(c) 询问，这里不再赘述。
类似地，我们尝试推一波 f \ast g 模 p 的贝尔级数：
\begin{aligned}
f_p(x) &= \sum_{k=0}^\infty f(p^k)x^k \\
&= 1+\sum_{k=1}^\infty p^cx^k = 1+{p^cx \over 1-x} \\
h_p(x) &= {1 \over 1-p^cx} \\
g_p(x) &= {1 \over h_p(x)} = 1-p^cx \\
(f \ast g)_p(x) &= f_p(x) g_p(x) \\
&= 1-p^cx + {p^cx-p^{2c}x^2 \over 1-x} \\
&= 1 + {p^c(1-p^c)x^2 \over 1-x} \\
&= 1 + \sum_{k=2}^\infty p^c(1-p^c)x^k
\end{aligned}
于是就可以愉快地利用前面的方法求 f 的前缀和了，时间复杂度 \Theta(c^2 + \sqrt N + N^{1 \over 4}c)。
例 3
求积性函数 f(n) = 2^{d(n)} 的前缀和，其中 d(n) 为 n 的可重质因数个数，对大质数取模。
对于质数 p，f(p) = 2。考虑设 h(n) = \sigma_0(n)，即 n 的因数个数，那么就满足了 h(p) = 2。
众所周知，\sigma_0(n) 的前缀和可以除法分块 \Theta(\sqrt n) 求，这里有一个常数优化的小技巧（推导过程不知为啥显示不出来，就不贴了）：
\sum_{i=1}^n \left\lfloor\frac n i\right\rfloor = 2\sum_{i=1}^{\sqrt n} \left\lfloor\frac n i\right\rfloor - \lfloor\sqrt n\rfloor^2
接下来我们写出 f \ast g 的贝尔级数：
\begin{aligned}
f_p(x) &= \sum_{k=0}^\infty f(p^k)x^k \\
&= \sum_{k=0}^\infty 2^kx^k = {1 \over 1-2x} \\
h_p(x) &= {1 \over (1-x)^2} \\
g_p(x) &= {1 \over h_p(x)} = (1-x)^2 \\
(f \ast g)_p(x) &= f_p(x) g_p(x) \\
&= {1-2x+x^2 \over 1-2x} \\
&= 1 + {x^2 \over 1-2x} \\
&= 1 + \sum_{k=2}^\infty 2^{k-2}x^k
\end{aligned}
时间复杂度 \Theta(\sqrt N \ln N)，常数较小所以能过。
例题
上面不是都有了吗？
后记
DGF 和贝尔级数更多地被用来简化推导过程、使过程更为直观、暴力，作为普通数论推导在生成函数方面的补充还是相当实用的。