狄利克雷卷积

本文介绍 Dirichlet 卷积和 Dirichlet 生成函数．

Dirichlet 卷积

数论函数 $f(n)$ 和 $g(n)$ 的 Dirichlet 卷积（Dirichlet convolution），记作 $f\ast g$，定义为数论函数

$$(f\ast g)(n)=\sum _{k\mid n}f(k)g\left(\frac{n}{k}\right)=\sum _{k\ell =n}f(k)g(\ell ).$$

Dirichlet 卷积是数论函数的重要运算．数论函数的许多性质都是通过这个运算挖掘出来的．

莫比乌斯反演 就是利用 $\epsilon =\mu \ast 1$ 对数论函数恒等式进行变形．

性质

Dirichlet 卷积具有一系列代数性质．

证明

为验证交换律，直接计算可知

$$(f\ast g)(n)=\sum _{k\ell =n}f(k)g(\ell )=(g\ast f)(n).$$

为验证结合律，直接计算可知

$$((f\ast g)\ast h)(n)=\sum _{k\ell m=n}f(k)g(\ell )h(m)=(f\ast (g\ast h))(n).$$

为验证分配律，直接计算可知

为验证 $\epsilon (n)$ 是单位元，直接计算可知

$$(f\ast \epsilon )(n)=\sum _{k\ell =n}f(k)\epsilon (\ell )=f(n).$$

第二个等号是因为 $\epsilon (\ell )$ 仅在 $\ell =1$ 即 $k=n$ 时取得非零值．

最后，需要证明 $f^{-1}$ 存在，当且仅当 $f(1)\ne 0$．对于任意 $f$，假设存在 $g$ 使得 $f\ast g=\epsilon$．这意味着

$$(f\ast g)(n)=\sum _{k\ell =n}f(k)g(\ell )=\epsilon (n).$$

这实际上给出了一系列关于 $g(n)$ 取值的方程组，从中可以直接求出 $g(n)$．特别地，当 $n=1$ 时，等式变为 $f(1)g(1)=1$，所以 $g$ 存在，至少要求 $f(1)\ne 0$．而只要 $f(1)\ne 0$，可以直接解出

$$g(n)=\frac{\epsilon (n)-\sum _{k\ell =n,k\ne 1}f(k)g(\ell )}{f(1)}.$$

它可以用于递归计算 $g(n)$ 的取值．因此，逆元 $g$ 存在，当且仅当 $f(1)\ne 0$．

用抽象代数的语言说，这些代数性质说明，全体数论函数在（逐点）加法运算和 Dirichlet 卷积运算下构成 交换环，且它的全体可逆元就是那些在 $n=1$ 处取非零值的函数．这个环称为 Dirichlet 环（Dirichlet ring）．

积性函数是一类特殊的数论函数．它对于 Dirichlet 卷积和 Dirichlet 逆都是封闭的．

证明

对于第一点，设 $h=f\ast g$，直接验证可知，对于 $n_1⟂n_2$，都有

其中，第三个等号利用了 $f,g$ 的积性，其改变求和顺序的逻辑是：当 $k$ 遍历 $n_1{n}_2$ 的因数时，$k$ 的素因子可以根据它是 $n_1$ 还是 $n_2$ 的素因子分为两类，将两类中的素因子（计重复）分别乘起来得到 $k_1$ 和 $k_2$，它们将分别遍历 $n_1$ 和 $n_2$ 的因数；反过来，根据 $n_1$ 和 $n_2$ 的因数 $k_1$ 和 $k_2$，总是可以得到 $n_1{n}_2$ 的因数 $k=k_1{k}_2$．

对于第二点，设 $g=f^{-1}$，考虑应用数学归纳法．首先，$g(1)=1/f(1)=1$．此时，逆元的递推公式可以写作

$$g(n)=\epsilon (n)-\sum _{k\ell =n,k\ne 1}f(k)g(\ell ).$$

所以，对于 $n_1⟂n_2$ 且 ，有

其中，第二个等号用到了归纳假设，即对于 且 ${\ell }_1⟂{\ell }_2$，条件 $g({\ell }_1{\ell }_2)=g({\ell }_1)g({\ell }_2)$ 成立．

用抽象代数的语言说，全体积性函数在 Dirichlet 卷积运算下构成 Dirichlet 环乘法群的 子群．

更为特殊的是完全积性函数．

证明

对于第一条，直接验证可知

其中，第三个等号用到了完全积性函数的性质：$\alpha (n)=\alpha (k)\alpha (\ell )$ 对所有 $n=k\ell$ 都成立．

对于第二条，利用第一条就有

$$(\alpha f)\ast (\alpha f^{-1})=\alpha (f\ast f^{-1})=\alpha \epsilon =\epsilon .$$

其中，最后一个等号只利用了 $\alpha (1)=1$．由逆元定义，$(\alpha f{)}^{-1}=\alpha f^{-1}$．

对于第三条，利用第二条和 $1^{-1}=\mu$ 可知，如果 $f$ 是完全积性函数，那么

$$f^{-1}=(1f{)}^{-1}=1^{-1}\cdot f=\mu f.$$

其中，$1$ 是常数函数．反过来，如果 $f$ 是积性函数且 $f^{-1}=\mu f$，那么只需要证明对于所有素数 $p$ 和 $e\in {\mathbf{N}}_{+}$，都有 $f(p^e)=f(p{)}^e$ 成立，就能证明 $f$ 是完全积性函数．为此，对 $e\in {\mathbf{N}}_{+}$ 应用数学归纳法．归纳起点 $e=1$ 处命题显然成立．对于任意 ，应用逆元递推公式，都有

其中，最后一个等号用到了归纳假设 $f(p^{e-1})=f(p{)}^{e-1}$．应用 $f^{-1}=\mu f$，就得到

$$f^{-1}(p^e)=\mu (p^e)f(p^e)=0.$$

代入前式，就得到

$$f(p^e)=f(p{)}^e.$$

所以，归纳步骤成立．原命题得证．

用抽象代数的语言说，如果 $\alpha$ 是完全积性函数，映射 $f\mapsto \alpha f$ 是 Dirichlet 环的 自同态．

Dirichlet 生成函数

与 Dirichlet 卷积紧密相关的是 Dirichlet 生成函数．

数论函数 $f(n)$——也就是数列 $\{f(n)\}$——对应的 Dirichlet 生成函数（Dirichlet series generating function，DGF）定义为形式 Dirichlet 级数（formal Dirichlet series）：

$$F(s)=\sum _{n=1}^{\mathrm{\infty }}\frac{f(n)}{n^s}.$$

级数中的 $s$ 是形式变元．常见的 Dirichlet 生成函数中，$s$ 往往可以看作是复变量，进而讨论 Dirichlet 级数的解析性质，但这超出了算法竞赛的范围．

Dirichlet 生成函数的乘积对应着相应的数论函数的 Dirichlet 卷积：

证明

直接验证：

利用 Dirichlet 卷积和 Dirichlet 生成函数乘积之间的对应关系，可以从 Dirichlet 生成函数的角度理解 Dirichlet 卷积的性质．由于形式 Dirichlet 级数的乘法运算满足交换律、结合律、对加法的分配律，数论函数的 Dirichlet 卷积运算满足同样的代数性质．

Euler 乘积

积性函数的特殊性同样反映在 Dirichlet 生成函数上．由于整数有 唯一分解定理，积性函数 $f(n)$ 的生成函数 $F(s)$ 可写成如下形式：

其中，${\nu }_p(n)$ 表示 $n$ 的素因数分解中 $p$ 的幂次．这意味着，$F(s)$ 可以分解为若干 $F_p(s)=\sum _{e=0}^{\mathrm{\infty }}f(p^e)p^{-es}$ 的乘积，且每个 $F_p(s)$ 对应的数论函数都只在 $p$ 的幂次处可能取非零值．这一无穷乘积也称为 Euler 乘积（Euler product）．如果 $F(s)$ 和 $G(s)$ 都能分解成类似的形式，那么它们的乘积同样如此；将这一观察对应到数论函数上，就是积性函数的 Dirichlet 卷积仍然是积性函数．

进一步地，如果 $f(n)$ 还是完全积性函数，那么 $f(p^e)=f(p{)}^e$，上式可以继续简化：

$$F(s)=\prod _{p\in \mathbf{P}}\sum _{e=0}^{\mathrm{\infty }}\frac{f(p{)}^e}{p^{es}}=\prod _{p\in \mathbf{P}}{(1-\frac{f(p)}{p^s})}^{-1}.$$

与积性函数不同，完全积性函数的 Dirichlet 生成函数的形式在乘法运算下并不具有封闭性，因此，完全积性函数的 Dirichlet 卷积和 Dirichlet 逆都未必是完全积性函数，但一定是积性函数．

Bell 级数

Euler 乘积说明，积性函数的 Dirichlet 生成函数可以分解为局部因子 $F_p(s)$ 的乘积．如果只关心单个素数处的信息，可以将 $p^{-s}$ 整体看作一个形式变元，这就得到了 Bell 级数．

对于积性函数 $f$ 和素数 $p$，定义 $f$ 关于 $p$ 的 Bell 级数（Bell series）为形式幂级数

$$f_p(x)=\sum _{e=0}^{\mathrm{\infty }}f(p^e)x^e=1+f(p)x+f(p^2)x^2+\cdots .$$

对比 Euler 乘积的表达式可知，$f_p(x)$ 就是将 $F_p(s)$ 中的 $p^{-s}$ 替换为 $x$ 的结果，即 $F_p(s)=f_p(p^{-s})$，从而

$$F(s)=\prod _{p\in \mathbf{P}}{f}_p(p^{-s}).$$

引入这一记号后可以看出，Dirichlet 卷积在局部化之后就是普通的幂级数乘法．

将 Dirichlet 生成函数的结果转译到 Bell 级数上，就得到如下性质：

1. 对于积性函数 $f,g$ 及任意素数 $p$，有 $(f\ast g{)}_p(x)=f_p(x)g_p(x)$．
2. 积性函数 $f$ 是完全积性函数，当且仅当对每个素数 $p$ 都有 $f_p(x)={\displaystyle \frac{1}{1-f(p)x}}$．
3. 积性函数的 Dirichlet 逆总是存在，且 $(f^{-1}{)}_p(x)={\displaystyle \frac{1}{f_p(x)}}$．

因为积性函数由它在素数幂处的取值唯一确定，所以积性函数与它的全体 Bell 级数 $\{f_p{\}}_{p\in \mathbf{P}}$ 是一一对应的．于是，关于积性函数的 Dirichlet 卷积的许多问题，都可以逐个素数地转化为形式幂级数的问题来讨论．相比直接使用 Dirichlet 生成函数，其形式上要简洁一些．例如，第三条性质说明，求 Dirichlet 逆只需逐个素数地求形式幂级数的逆；在实际计算中，因为只需要 $p^e\le n$ 的部分，每个素数至多截断到 $x^{\lfloor {\log }_{p}n\rfloor }$ 项．

例子

前文例子中的积性函数，对应的 Bell 级数如下：

$f$	$\epsilon$	$1$	$\mu$	${\mathrm{id}}_k$	$\phi$	${\sigma }_k$	$|\mu |={\mu }^2$
$f_p(x)$	$1$	${\displaystyle \frac{1}{1-x}}$	$1-x$	${\displaystyle \frac{1}{1-p^{k}x}}$	${\displaystyle \frac{1-x}{1-px}}$	${\displaystyle \frac{1}{(1-x)(1-p^{k}x)}}$	$1+x$

利用上表，常见的 Dirichlet 卷积关系都可以直接验证．例如 $\mu \ast 1=\epsilon$ 对应

$$(1-x)\cdot \frac{1}{1-x}=1,$$

而 $\phi \ast 1=\mathrm{id}$ 对应

$$\frac{1-x}{1-px}\cdot \frac{1}{1-x}=\frac{1}{1-px}.$$

应用

Dirichlet 生成函数可以用于将数论函数表示为 Dirichlet 卷积．

例如在杜教筛的过程中，要计算数论函数 $f$ 的前缀和，需要找到另一个数论函数 $g$ 使得 $f\ast g$ 和 $g$ 都可以快速求前缀和．可以利用 Dirichlet 生成函数推导这一过程．

以杜教筛一节的例题 Luogu P3768 简单的数学题 为例，需要对 $f(n)=n^2\phi (n)$ 构造满足上述条件的数论函数 $g(n)$．由于 $f$ 是积性函数，它的 Dirichlet 生成函数为

$$F(s)=\prod _{p\in \mathbf{P}}(1+\sum _{k=1}^{\mathrm{\infty }}\frac{p^{3k-1}(p-1)}{p^{ks}})=\prod _{p\in \mathbf{P}}\frac{1-p^{2-s}}{1-p^{3-s}}=\frac{\zeta (s-3)}{\zeta (s-2)}.$$

对比幂函数的 Dirichlet 生成函数可知，只要取 $g={\mathrm{id}}_2$，就有 $f\ast g={\mathrm{id}}_3$．两者都是可以快速计算前缀和的．

由于常见问题中的数论函数都是积性函数，实践中利用 Bell 级数往往更加方便．例如，刚刚的例子中 $f(n)$ 的 Bell 级数可以直接由 $f(p^e)=p^{3e-1}(p-1)$ 推得为

$$f_p(x)=1+\frac{p-1}{p}\sum _{e=1}^{\mathrm{\infty }}(p^{3}x{)}^e=1+\frac{(p-1)p^{2}x}{1-p^{3}x}=\frac{1-p^{2}x}{1-p^{3}x}.$$

对比幂函数的 Bell 级数立即得到 $f\ast {\mathrm{id}}_2={\mathrm{id}}_3$．

Dirichlet 卷积的计算

本节讨论 Dirichlet 卷积的计算问题，即给定序列 $\{f(k){\}}_{k=1}^n$ 和 $\{g(k){\}}_{k=1}^n$，求解 Dirichlet 卷积 $h=f\ast g$ 的前若干项 $\{h(k){\}}_{k=1}^n$ 的问题．根据涉及到的函数性质，算法的复杂度也略有不同．

一般情形

如果 $f,g,h$ 都没有特殊性质，那么 Dirichlet 卷积的计算只能利用其定义：

$$h(n)=\sum _{k\ell =n}f(k)g(\ell ).$$

枚举 $k$ 和 $\ell$，将贡献 $f(k)g(\ell )$ 累加到 $h(k\ell )$ 上即可．枚举复杂度为

$$O\left(\sum _{k=1}^n\frac{n}{k}\right)=O(n\log n).$$

参考实现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

// Compute the Dirichlet convolution h = f * g.
auto dirichlet_convolute(const std::vector<int>& f, const std::vector<int>& g) {
  int n = f.size() - 1;
  std::vector<int> h(n + 1);
  for (int k = 1; k <= n; ++k) {
    for (int d = 1; k * d <= n; ++d) {
      h[k * d] += f[k] * g[d];
    }
  }
  return h;
}

与积性函数卷积的情形

如果 $g$ 是积性函数，那么可以利用 Euler 乘积加速 Dirichlet 卷积的计算．计算 $h$ 相当于计算它的 Dirichlet 生成函数 $H$ 中各项的系数．由于

$$H(s)=F(s)G(s)=F(s)\prod _{p\in \mathbf{P}}{G}_p(s).$$

其中，$G_p(s)$ 是 $G(s)$ 的 Euler 乘积分解中的因式，它只包含 $p$ 的幂次处的系数：

$$G_p(s)=\sum _{p^k\le n}\frac{g(p^k)}{p^{ks}}=1+\frac{g(p)}{p^s}+\frac{g(p^2)}{p^{2s}}+\cdots .$$

那么，从 $F(s)$ 开始，遍历所有不超过 $n$ 的素数 $p$，将 $G_p(s)$ 逐一乘上去，同样可以得到最终结果 $H(s)$．将 $G_p(s)$ 乘上去时，直接应用一般情形中的暴力枚举算法即可．总枚举次数

$$\sum _{p\in \mathbf{P},p\le n}\sum _{k=1}^{\mathrm{\infty }}\lfloor \frac{n}{p^k}\rfloor \le \sum _{p\in \mathbf{P},p\le n}\frac{n}{p-1}\le \sum _{p\in \mathbf{P},p\le n}\frac{2n}{p}\in O(n\log \log n).$$

最后一步复杂度的估计与 Eratosthenes 筛法 复杂度的证明一致．所以，本算法的时间复杂度为 $O(n\log \log n)$．

参考实现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

// Compute the Dirichlet convolution h = f * g.
// Assume that g is multiplicative.
auto dirichlet_convolute(const std::vector<int>& f, const std::vector<int>& g) {
  int n = f.size() - 1;
  std::vector<int> h(f);
  std::vector<bool> vis(n + 1);
  for (int i = 2; i <= n; ++i) {
    if (vis[i]) continue;
    // Reverse the order for in-place computation.
    for (int k = n / i * i; k; k -= i) {
      vis[k] = true;
      int d = k;
      while (true) {
        d /= i;
        h[k] += h[d] * g[k / d];
        if (d % i) break;
      }
    }
  }
  return h;
}

特别地，当积性函数 $g$ 是完全积性函数或其 Dirichlet 逆时，例如当 $g=1$ 或 $g=\mu$ 时，算法可以进一步简化．此时，Dirichlet 卷积 $h=f\ast g$ 的计算可以采用常数更小的 Dirichlet 前缀和/差分 算法，但是算法时间复杂度仍为 $O(n\log \log n)$．

结果为积性函数的情形

最后，考虑 $h$ 是积性函数的情形．特别地，当 $f,g$ 都是积性函数时，$h=f\ast g$ 就是积性函数．要计算 $h$，只需要确定它在素数幂处的取值，就可以通过 线性筛 在 $O(n)$ 时间内计算．而对于素数幂 $p^e$ 处的取值 $h(p^e)$ 直接暴力计算即可：

$$h(p^e)=\sum _{i=0}^{e}f(p^i)g(p^{e-i}).$$

这些暴力计算需要的枚举次数为

因此，这一算法的总时间复杂度为 $O(n)$．

参考实现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

// Compute the Dirichlet convolution h = f * g.
// Assume that h is multiplicative.
auto dirichlet_convolute(const std::vector<int>& f, const std::vector<int>& g) {
  int n = f.size() - 1;
  std::vector<int> h(n + 1), primes, rem(n + 1), lpf(n + 1);
  std::vector<bool> vis(n + 1);
  h[1] = 1;
  for (int x = 2; x <= n; ++x) {
    if (!vis[x]) {
      primes.push_back(x);
      rem[x] = 1;
      lpf[x] = x;
    }
    for (int p : primes) {
      if (x * p > n) break;
      vis[x * p] = true;
      rem[x * p] = x % p ? x : rem[x];
      lpf[x * p] = p;
      if (x % p == 0) break;
    }
    if (rem[x] == 1) {  // prime powers.
      for (int k = x; k; k /= lpf[x]) {
        h[x] += f[k] * g[x / k];
      }
    } else {  // other cases.
      h[x] = h[rem[x]] * h[x / rem[x]];
    }
  }
  return h;
}

参考资料与注释

• Dirichlet convolution - Wikipedia
• Dirichlet series - Wikipedia
• Euler product - Wikipedia
• Bell series - Wikipedia
• Dirichlet 積と、数論関数の累積和 by maspy
• 杜教筛（+ 贝尔级数 + powerful number）by command_block - 洛谷

本页面最近更新：2026/9/24 22:07:06，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：c-forrest, Tiphereth-A, billchenchina, CCXXXI, danielqfmai, Enter-tainer, Great-designer, HeRaNO, lychees, Menci, Nanarikom, ouuan, shuzhouliu, sshwy
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用