跳转至

# 狄利克雷卷积

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

## Dirichlet 卷积

数论函数 𝑓(𝑛)f(n) 和 𝑔(𝑛)g(n) 的 Dirichlet 卷积（Dirichlet convolution），记作 𝑓 ∗𝑔 f∗g，定义为数论函数

(𝑓∗𝑔)(𝑛)=∑𝑘∣𝑛 𝑓(𝑘)𝑔(𝑛 𝑘)=∑𝑘 ℓ=𝑛 𝑓(𝑘)𝑔(ℓ).(f∗g)(n)=∑k∣n f(k)g(n k)=∑k ℓ=n f(k)g(ℓ).

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

例子

1. 单位函数 𝜀 ε 是莫比乌斯函数 𝜇 μ 和常数函数 1 1 的 Dirichlet 卷积：

𝜀=𝜇∗1⟺𝜀(𝑛)=∑𝑑∣𝑛 𝜇(𝑑).ε=μ∗1⟺ε(n)=∑d∣n μ(d).

1. 除数个数函数 𝜏 τ 是常数函数 1 1 和它自身的 Dirichlet 卷积：

𝜏=1∗1⟺𝜏(𝑛)=∑𝑑∣𝑛 1.τ=1∗1⟺τ(n)=∑d∣n 1.

1. 除数和函数 𝜎 σ 是恒等函数 i d id 和常数函数 1 1 的 Dirichlet 卷积：

𝜎=i d∗1⟺𝜎(𝑛)=∑𝑑∣𝑛 𝑑.σ=id∗1⟺σ(n)=∑d∣n d.

1. 欧拉函数 𝜑 φ 是恒等函数 i d id 和莫比乌斯函数 𝜇 μ 的 Dirichlet 卷积：

𝜑=i d∗𝜇⟺𝜑(𝑛)=∑𝑑∣𝑛 𝑑⋅𝜇(𝑛 𝑑).φ=id∗μ⟺φ(n)=∑d∣n d⋅μ(n d).

莫比乌斯反演 就是利用 𝜀 =𝜇 ∗1 ε=μ∗1 对数论函数恒等式进行变形．

### 性质

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

定理

设 𝑓,𝑔,ℎ f,g,h 都是数论函数．那么，有：

1. 交换律：𝑓 ∗𝑔 =𝑔 ∗𝑓 f∗g=g∗f．
2. 结合律：(𝑓 ∗𝑔) ∗ℎ =𝑓 ∗(𝑔 ∗ℎ)(f∗g)∗h=f∗(g∗h)．
3. 分配律：(𝑓 +𝑔) ∗ℎ =𝑓 ∗ℎ +𝑔 ∗ℎ(f+g)∗h=f∗h+g∗h．
4. 单位元：𝑓 ∗𝜀 =𝜀 ∗𝑓 =𝑓 f∗ε=ε∗f=f，其中，𝜀(𝑛) =[𝑛 =1]ε(n)=[n=1] 是卷积单位元，[ ⋅][⋅] 是 Iverson 括号．
5. 逆元：当且仅当 𝑓(1) ≠0 f(1)≠0 时，存在 𝑔 g 使得 𝑓 ∗𝑔 =𝑔 ∗𝑓 =𝜀 f∗g=g∗f=ε，且 𝑔 g 称为 𝑓 f 的 Dirichlet 逆元（Dirichlet inverse），可以记作 𝑓−1 f−1．而且，逆元 𝑔 g 满足递推公式

𝑔(𝑛)=𝜀(𝑛)−∑𝑘 ℓ=𝑛, 𝑘≠1 𝑓(𝑘)𝑔(ℓ)𝑓(1).g(n)=ε(n)−∑k ℓ=n, k≠1 f(k)g(ℓ)f(1).
证明

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

(𝑓∗𝑔)(𝑛)=∑𝑘 ℓ=𝑛 𝑓(𝑘)𝑔(ℓ)=(𝑔∗𝑓)(𝑛).(f∗g)(n)=∑k ℓ=n f(k)g(ℓ)=(g∗f)(n).

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

((𝑓∗𝑔)∗ℎ)(𝑛)=∑𝑘 ℓ 𝑚=𝑛 𝑓(𝑘)𝑔(ℓ)ℎ(𝑚)=(𝑓∗(𝑔∗ℎ))(𝑛).((f∗g)∗h)(n)=∑k ℓ m=n f(k)g(ℓ)h(m)=(f∗(g∗h))(n).

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

((𝑓+𝑔)∗ℎ)(𝑛)=∑𝑘 ℓ=𝑛(𝑓(𝑘)+𝑔(𝑘))ℎ(ℓ)=∑𝑘 ℓ=𝑛 𝑓(𝑘)ℎ(ℓ)+∑𝑘 ℓ=𝑛 𝑔(𝑘)ℎ(ℓ)=(𝑓∗ℎ+𝑔∗ℎ)(𝑛).((f+g)∗h)(n)=∑k ℓ=n(f(k)+g(k))h(ℓ)=∑k ℓ=n f(k)h(ℓ)+∑k ℓ=n g(k)h(ℓ)=(f∗h+g∗h)(n).

为验证 𝜀(𝑛)ε(n) 是单位元，直接计算可知

(𝑓∗𝜀)(𝑛)=∑𝑘 ℓ=𝑛 𝑓(𝑘)𝜀(ℓ)=𝑓(𝑛).(f∗ε)(n)=∑k ℓ=n f(k)ε(ℓ)=f(n).

第二个等号是因为 𝜀(ℓ)ε(ℓ) 仅在 ℓ =1 ℓ=1 即 𝑘 =𝑛 k=n 时取得非零值．

最后，需要证明 𝑓−1 f−1 存在，当且仅当 𝑓(1) ≠0 f(1)≠0．对于任意 𝑓 f，假设存在 𝑔 g 使得 𝑓 ∗𝑔 =𝜀 f∗g=ε．这意味着

(𝑓∗𝑔)(𝑛)=∑𝑘 ℓ=𝑛 𝑓(𝑘)𝑔(ℓ)=𝜀(𝑛).(f∗g)(n)=∑k ℓ=n f(k)g(ℓ)=ε(n).

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

𝑔(𝑛)=𝜀(𝑛)−∑𝑘 ℓ=𝑛, 𝑘≠1 𝑓(𝑘)𝑔(ℓ)𝑓(1).g(n)=ε(n)−∑k ℓ=n, k≠1 f(k)g(ℓ)f(1).

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

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

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

定理

设 𝑓,𝑔 f,g 是积性函数，那么，𝑓 ∗𝑔 f∗g 也是积性函数．而且，逆元 𝑓−1 f−1 一定存在，它也是积性函数．

证明

对于第一点，设 ℎ =𝑓 ∗𝑔 h=f∗g，直接验证可知，对于 𝑛 1 ⟂𝑛 2 n 1⟂n 2，都有

ℎ(𝑛 1)ℎ(𝑛 2)=(∑𝑘 1 ℓ 1=𝑛 1 𝑓(𝑘 1)𝑔(ℓ 1))(∑𝑘 2 ℓ 2=𝑛 2 𝑓(𝑘 2)𝑔(ℓ 2))=∑𝑘 1 ℓ 1=𝑛 1, 𝑘 2 ℓ 2=𝑛 2 𝑓(𝑘 1)𝑓(𝑘 2)𝑔(ℓ 1)𝑔(ℓ 2)=∑𝑘 ℓ=𝑛 1 𝑛 2 𝑓(𝑘)𝑔(ℓ)=ℎ(𝑛 1 𝑛 2).h(n 1)h(n 2)=(∑k 1 ℓ 1=n 1 f(k 1)g(ℓ 1))(∑k 2 ℓ 2=n 2 f(k 2)g(ℓ 2))=∑k 1 ℓ 1=n 1, k 2 ℓ 2=n 2 f(k 1)f(k 2)g(ℓ 1)g(ℓ 2)=∑k ℓ=n 1 n 2 f(k)g(ℓ)=h(n 1 n 2).

其中，第三个等号改变求和顺序的逻辑是：当 𝑘 k 遍历 𝑛 1 𝑛 2 n 1 n 2 的因数时，𝑘 k 的素因子可以根据它是 𝑛 1 n 1 还是 𝑛 2 n 2 的素因子分为两类，将两类中的素因子（计重复）分别乘起来得到 𝑘 1 k 1 和 𝑘 2 k 2，它们将分别遍历 𝑛 1 n 1 和 𝑛 2 n 2 的因数；反过来，根据 𝑛 1 n 1 和 𝑛 2 n 2 的因数 𝑘 1 k 1 和 𝑘 2 k 2，总是可以得到 𝑛 1 𝑛 2 n 1 n 2 的因数 𝑘 =𝑘 1 𝑘 2 k=k 1 k 2．

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

𝑔(𝑛)=𝜀(𝑛)−∑𝑘 ℓ=𝑛, 𝑘≠1 𝑓(𝑘)𝑔(ℓ).g(n)=ε(n)−∑k ℓ=n, k≠1 f(k)g(ℓ).

所以，对于 𝑛 1 ⟂𝑛 2 n 1⟂n 2 且 𝑛 1 𝑛 2 >1 n 1 n 2>1，有

𝑔(𝑛 1 𝑛 2)=−∑𝑘 ℓ=𝑛 1 𝑛 2, 𝑘≠1 𝑓(𝑘)𝑔(ℓ)=−∑𝑘 1 ℓ 1=𝑛 1, 𝑘 2 ℓ 2=𝑛 2, 𝑘 1 𝑘 2≠1 𝑓(𝑘 1)𝑓(𝑘 2)𝑔(ℓ 1)𝑔(ℓ 2)=𝑓(1)𝑓(1)𝑔(𝑛 1)𝑔(𝑛 2)−∑𝑘 1 ℓ 1=𝑛 1, 𝑘 2 ℓ 2=𝑛 2 𝑓(𝑘 1)𝑓(𝑘 2)𝑔(ℓ 1)𝑔(ℓ 2)=𝑔(𝑛 1)𝑔(𝑛 2)−(∑𝑘 1 ℓ 1=𝑛 1 𝑓(𝑘 1)𝑔(ℓ 1))(∑𝑘 2 ℓ 2=𝑛 2 𝑓(𝑘 2)𝑔(ℓ 2))=𝑔(𝑛 1)𝑔(𝑛 2)−𝜀(𝑛 1)𝜀(𝑛 2)=𝑔(𝑛 1)𝑔(𝑛 2).g(n 1 n 2)=−∑k ℓ=n 1 n 2, k≠1 f(k)g(ℓ)=−∑k 1 ℓ 1=n 1, k 2 ℓ 2=n 2, k 1 k 2≠1 f(k 1)f(k 2)g(ℓ 1)g(ℓ 2)=f(1)f(1)g(n 1)g(n 2)−∑k 1 ℓ 1=n 1, k 2 ℓ 2=n 2 f(k 1)f(k 2)g(ℓ 1)g(ℓ 2)=g(n 1)g(n 2)−(∑k 1 ℓ 1=n 1 f(k 1)g(ℓ 1))(∑k 2 ℓ 2=n 2 f(k 2)g(ℓ 2))=g(n 1)g(n 2)−ε(n 1)ε(n 2)=g(n 1)g(n 2).

其中，第二个等号用到了归纳假设，即对于 ℓ 1 ℓ 2 <𝑛 1 𝑛 2 ℓ 1 ℓ 2<n 1 n 2 且 ℓ 1 ⟂ℓ 2 ℓ 1⟂ℓ 2，条件 𝑔(ℓ 1 ℓ 2) =𝑔(ℓ 1)𝑔(ℓ 2)g(ℓ 1 ℓ 2)=g(ℓ 1)g(ℓ 2) 成立．

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

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

定理

设 𝛼 α 是完全积性函数，𝑓,𝑔 f,g 是数论函数．那么，有：

1. 分配律：(𝛼 𝑓) ∗(𝛼 𝑔) =𝛼 ⋅(𝑓 ∗𝑔)(α f)∗(α g)=α⋅(f∗g)．
2. 逆元：(𝛼 𝑓)−1 =𝛼 𝑓−1(α f)−1=α f−1，只要 𝑓−1 f−1 存在．
3. 积性函数 𝑓 f 是完全积性函数，当且仅当 𝑓−1 =𝜇 𝑓 f−1=μ f，其中，𝜇 μ 是 莫比乌斯函数．

证明

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

((𝛼 𝑓)∗(𝛼 𝑔))(𝑛)=∑𝑘 ℓ=𝑛(𝛼 𝑓)(𝑘)(𝛼 𝑔)(ℓ)=∑𝑘 ℓ=𝑛 𝛼(𝑘)𝑓(𝑘)𝛼(ℓ)𝑔(ℓ)=∑𝑘 ℓ=𝑛 𝛼(𝑛)𝑓(𝑘)𝑔(ℓ)=𝛼(𝑛)(𝑓∗𝑔)(𝑛).((α f)∗(α g))(n)=∑k ℓ=n(α f)(k)(α g)(ℓ)=∑k ℓ=n α(k)f(k)α(ℓ)g(ℓ)=∑k ℓ=n α(n)f(k)g(ℓ)=α(n)(f∗g)(n).

其中，第三个等号用到了完全积性函数的性质：𝛼(𝑛) =𝛼(𝑘)𝛼(ℓ)α(n)=α(k)α(ℓ) 对所有 𝑛 =𝑘 ℓ n=k ℓ 都成立．

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

(𝛼 𝑓)∗(𝛼 𝑓−1)=𝛼(𝑓∗𝑓−1)=𝛼 𝜀=𝜀.(α f)∗(α f−1)=α(f∗f−1)=α ε=ε.

其中，最后一个等号只利用了 𝛼(1) =1 α(1)=1．由逆元定义，(𝛼 𝑓)−1 =𝛼 𝑓−1(α f)−1=α f−1．

对于第三条，利用第二条和 1−1 =𝜇 1−1=μ 可知，如果 𝑓 f 是完全积性函数，那么

𝑓−1=(1 𝑓)−1=1−1⋅𝑓=𝜇 𝑓.f−1=(1 f)−1=1−1⋅f=μ f.

其中，1 1 是常数函数．反过来，如果 𝑓 f 是积性函数且 𝑓−1 =𝜇 𝑓 f−1=μ f，那么只需要证明对于所有素数 𝑝 p 和 𝑒 ∈𝐍+e∈N+，都有 𝑓(𝑝 𝑒) =𝑓(𝑝)𝑒 f(p e)=f(p)e 成立，就能证明 𝑓 f 是完全积性函数．为此，对 𝑒 ∈𝐍+e∈N+ 应用数学归纳法．归纳起点 𝑒 =1 e=1 处命题显然成立．对于任意 𝑒 >1 e>1，应用逆元递推公式，都有

𝑓−1(𝑝 𝑒)=−𝑒∑𝑖=1 𝑓(𝑝 𝑖)𝑓−1(𝑝 𝑒−𝑖)=−𝑒∑𝑖=1 𝑓(𝑝 𝑖)𝜇(𝑝 𝑒−𝑖)𝑓(𝑝 𝑒−𝑖)=−𝑓(𝑝 𝑒)𝑓(1)𝜇(1)−𝑓(𝑝 𝑒−1)𝜇(𝑝)𝑓(𝑝)=−𝑓(𝑝 𝑒)+𝑓(𝑝)𝑒.f−1(p e)=−∑i=1 e f(p i)f−1(p e−i)=−∑i=1 e f(p i)μ(p e−i)f(p e−i)=−f(p e)f(1)μ(1)−f(p e−1)μ(p)f(p)=−f(p e)+f(p)e.

其中，最后一个等号用到了归纳假设 𝑓(𝑝 𝑒−1) =𝑓(𝑝)𝑒−1 f(p e−1)=f(p)e−1．应用 𝑓−1 =𝜇 𝑓 f−1=μ f，就得到

𝑓−1(𝑝 𝑒)=𝜇(𝑝 𝑒)𝑓(𝑝 𝑒)=0.f−1(p e)=μ(p e)f(p e)=0.

代入前式，就得到

𝑓(𝑝 𝑒)=𝑓(𝑝)𝑒.f(p e)=f(p)e.

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

用抽象代数的语言说，如果 𝛼 α 是完全积性函数，映射 𝑓 ↦𝛼 𝑓 f↦α f 是 Dirichlet 环的 自同态．

## Dirichlet 生成函数

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

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

𝐹(𝑠)=∞∑𝑛=1 𝑓(𝑛)𝑛 𝑠.F(s)=∑n=1∞f(n)n s.

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

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

定理

对于数论函数 𝑓,𝑔 f,g 及其 Dirichlet 生成函数 𝐹,𝐺 F,G，它们的 Dirichlet 卷积 𝑓 ∗𝑔 f∗g 的生成函数等于 𝐹 ⋅𝐺 F⋅G．

证明

直接验证：

𝐹(𝑠)𝐺(𝑠)=(∞∑𝑘=1 𝑓(𝑘)𝑘 𝑠)(∞∑ℓ=1 𝑔(ℓ)ℓ 𝑠)=∞∑𝑘=1∞∑ℓ=1 𝑓(𝑘)𝑔(ℓ)(𝑘 ℓ)𝑠=∞∑𝑛=1∑𝑘 ℓ=𝑛 𝑓(𝑘)𝑔(ℓ)𝑛 𝑠=∞∑𝑛=1(𝑓∗𝑔)(𝑛)𝑛 𝑠.F(s)G(s)=(∑k=1∞f(k)k s)(∑ℓ=1∞g(ℓ)ℓ s)=∑k=1∞∑ℓ=1∞f(k)g(ℓ)(k ℓ)s=∑n=1∞∑k ℓ=n f(k)g(ℓ)n s=∑n=1∞(f∗g)(n)n s.

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

### Euler 乘积

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

𝐹(𝑠)=∞∑𝑛=1 𝑓(𝑛)𝑛 𝑠=∞∑𝑛=1∏𝑝∈𝐏 𝑓(𝑝 𝑒)𝑝 𝑒 𝑠=∏𝑝∈𝐏∞∑𝑒=0 𝑓(𝑝 𝑒)𝑝 𝑒 𝑠=∏𝑝∈𝐏(1+𝑓(𝑝)𝑝 𝑠+𝑓(𝑝 2)𝑝 2 𝑠+𝑓(𝑝 3)𝑝 3 𝑠+⋯).F(s)=∑n=1∞f(n)n s=∑n=1∞∏p∈P f(p e)p e s=∏p∈P∑e=0∞f(p e)p e s=∏p∈P(1+f(p)p s+f(p 2)p 2 s+f(p 3)p 3 s+⋯).

这意味着，𝐹(𝑠)F(s) 可以分解为若干 𝐹 𝑝(𝑠)F p(s) 的乘积，且每个 𝐹 𝑝(𝑠)F p(s) 对应的数论函数都只在 𝑝 p 的幂次处可能取非零值．这一无穷乘积也称为 Euler 乘积（Euler product）．如果 𝐹(𝑠)F(s) 和 𝐺(𝑠)G(s) 都能分解成类似的形式，那么它们的乘积同样如此；将这一观察对应到数论函数上，就是积性函数的 Dirichlet 卷积仍然是积性函数．

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

𝐹(𝑠)=∏𝑝∈𝐏∞∑𝑒=0 𝑓(𝑝)𝑒 𝑝 𝑒 𝑠=∏𝑝∈𝐏(1−𝑓(𝑝)𝑝 𝑠)−1.F(s)=∏p∈P∑e=0∞f(p)e p e s=∏p∈P(1−f(p)p s)−1.

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

例子

1. 单位函数 𝜀(𝑛)ε(n) 是完全积性函数．它的 Dirichlet 生成函数是关于不定元 𝑠 s 的常值函数

   𝐸(𝑠)=∞∑𝑛=1 𝜀(𝑛)𝑛 𝑠=1.E(s)=∑n=1∞ε(n)n s=1.

2. 常数函数 1(𝑛)1(n) 是完全积性函数．它的 Dirichlet 生成函数是 Riemann 函数

   𝐼(𝑠)=∞∑𝑛=1 1 𝑛 𝑠=∏𝑝∈𝐏 1 1−𝑝−𝑠=𝜁(𝑠).I(s)=∑n=1∞1 n s=∏p∈P 1 1−p−s=ζ(s).

3. 莫比乌斯函数 𝜇(𝑛)μ(n) 是常数函数的 Dirichlet 逆．它的 Dirichlet 生成函数是 𝜁(𝑠)ζ(s) 的倒数：

   𝑀(𝑠)=∞∑𝑛=1 𝜇(𝑛)𝑛 𝑠=∏𝑝∈𝐏(1−𝑝−𝑠)=1 𝜁(𝑠).M(s)=∑n=1∞μ(n)n s=∏p∈P(1−p−s)=1 ζ(s).

4. 幂函数 i d 𝑘⁡(𝑛) =𝑛 𝑘 id k⁡(n)=n k 是完全积性函数．特别地，当 𝑘 =0 k=0 时，它就是常数函数；当 𝑘 =1 k=1 时，它就是恒等函数．它的 Dirichlet 生成函数是

   𝐼 𝑘(𝑠)=∞∑𝑛=1 𝑛 𝑘 𝑛 𝑠=∏𝑝∈𝐏 1 1−𝑝 𝑘−𝑠=𝜁(𝑠−𝑘).I k(s)=∑n=1∞n k n s=∏p∈P 1 1−p k−s=ζ(s−k).

5. 欧拉函数 𝜑(𝑛)φ(n) 是积性函数．它的 Dirichlet 生成函数是

   Φ(𝑠)=∏𝑝∈𝐏(1+𝑝−1 𝑝 𝑠+𝑝(𝑝−1)𝑝 2 𝑠+𝑝 2(𝑝−1)𝑝 3 𝑠+⋯)=∏𝑝∈𝐏(1 1−𝑝 1−𝑠−1 𝑝 𝑠 1 1−𝑝 1−𝑠)=∏𝑝∈𝐏 1−𝑝−𝑠 1−𝑝 1−𝑠=𝜁(𝑠−1)𝜁(𝑠).Φ(s)=∏p∈P(1+p−1 p s+p(p−1)p 2 s+p 2(p−1)p 3 s+⋯)=∏p∈P(1 1−p 1−s−1 p s 1 1−p 1−s)=∏p∈P 1−p−s 1−p 1−s=ζ(s−1)ζ(s).

   结合幂函数的 Dirichlet 函数表达式，就得到 i d =𝜑 ∗1 id=φ∗1．

6. 约数函数 𝜎 𝑘(𝑛) =∑𝑑∣𝑛 𝑑 𝑘 σ k(n)=∑d∣n d k 是积性函数．它的 Dirichlet 生成函数是

   Σ 𝑘(𝑠)=∏𝑝∈𝐏(1+1+𝑝 𝑘 𝑝 𝑠+1+𝑝 𝑘+𝑝 2 𝑘 𝑝 2 𝑠+1+𝑝 𝑘+𝑝 2 𝑘+𝑝 3 𝑘 𝑝 3 𝑠+⋯)=∏𝑝∈𝐏 1 1−𝑝 𝑘((1−𝑝 𝑘)+1−𝑝 2 𝑘 𝑝 𝑠+1−𝑝 3 𝑘 𝑝 2 𝑠+1−𝑝 4 𝑘 𝑝 3 𝑘+⋯)=∏𝑝∈𝐏 1 1−𝑝 𝑘(1 1−𝑝−𝑠−𝑝 𝑘 1−𝑝 𝑘−𝑠)=∏𝑝∈𝐏 1(1−𝑝−𝑠)(1−𝑝 𝑘−𝑠)=𝜁(𝑠−𝑘)𝜁(𝑠).Σ k(s)=∏p∈P(1+1+p k p s+1+p k+p 2 k p 2 s+1+p k+p 2 k+p 3 k p 3 s+⋯)=∏p∈P 1 1−p k((1−p k)+1−p 2 k p s+1−p 3 k p 2 s+1−p 4 k p 3 k+⋯)=∏p∈P 1 1−p k(1 1−p−s−p k 1−p k−s)=∏p∈P 1(1−p−s)(1−p k−s)=ζ(s−k)ζ(s).

   结合幂函数的 Dirichlet 表达式，就得到 𝜎 𝑘 =i d 𝑘 ∗1 σ k=id k∗1．这正是 𝜎 𝑘 σ k 的定义式．

7. 无平方因子数的指示函数 𝑢(𝑛) =|𝜇(𝑛)|u(n)=|μ(n)| 是积性函数．它的 Dirichlet 生成函数是

   𝑈(𝑠)=∏𝑝∈𝐏(1+𝑝−𝑠)=∏𝑝∈𝐏 1−𝑝−2 𝑠 1−𝑝−𝑠=𝜁(𝑠)𝜁(2 𝑠).U(s)=∏p∈P(1+p−s)=∏p∈P 1−p−2 s 1−p−s=ζ(s)ζ(2 s).

### 应用

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

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

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

𝐹(𝑠)=∏𝑝∈𝐏(1+∞∑𝑘=1 𝑝 3 𝑘−1(𝑝−1)𝑝 𝑘 𝑠)=∏𝑝∈𝐏 1−𝑝 2−𝑠 1−𝑝 3−𝑠=𝜁(𝑠−3)𝜁(𝑠−2).F(s)=∏p∈P(1+∑k=1∞p 3 k−1(p−1)p k s)=∏p∈P 1−p 2−s 1−p 3−s=ζ(s−3)ζ(s−2).

对比幂函数的 Dirichlet 生成函数可知，只要取 𝑔 =i d 2 g=id 2，就有 𝑓 ∗𝑔 =i d 3 f∗g=id 3．两者都是可以快速计算前缀和的．

## Dirichlet 卷积的计算

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

### 一般情形

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

ℎ(𝑛)=∑𝑘 ℓ=𝑛 𝑓(𝑘)𝑔(ℓ).h(n)=∑k ℓ=n f(k)g(ℓ).

枚举 𝑘 k 和 ℓ ℓ，将贡献 𝑓(𝑘)𝑔(ℓ)f(k)g(ℓ) 累加到 ℎ(𝑘 ℓ)h(k ℓ) 上即可．枚举复杂度为

𝑂(𝑛∑𝑘=1 𝑛 𝑘)=𝑂(𝑛 l o g⁡𝑛).O(∑k=1 n n k)=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)∏p∈P G p(s).

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

𝐺 𝑝(𝑠)=∑𝑝 𝑘≤𝑛 𝑓(𝑝 𝑘)𝑝 𝑘 𝑠=1+𝑓(𝑝)𝑝 𝑠+𝑓(𝑝 2)𝑝 2 𝑠+⋯.G p(s)=∑p k≤n f(p k)p k s=1+f(p)p s+f(p 2)p 2 s+⋯.

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

∑𝑝∈𝐏, 𝑝≤𝑛∞∑𝑘=1⌊𝑛 𝑝 𝑘⌋≤∑𝑝∈𝐏, 𝑝≤𝑛 𝑛 𝑝−1≤∑𝑝∈𝐏, 𝑝≤𝑛 2 𝑛 𝑝∈𝑂(𝑛 l o g⁡l o g⁡𝑛).∑p∈P, p≤n∑k=1∞⌊n p k⌋≤∑p∈P, p≤n n p−1≤∑p∈P, p≤n 2 n p∈O(n log⁡log⁡n).

最后一步复杂度的估计与 Eratosthenes 筛法 复杂度的证明一致．所以，本算法的时间复杂度为 𝑂(𝑛 l o g⁡l o g⁡𝑛)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 逆时，例如当 𝑔 =1 g=1 或 𝑔 =𝜇 g=μ 时，那么算法可以进一步简化．此时，Dirichlet 卷积 ℎ =𝑓 ∗𝑔 h=f∗g 的计算可以采用常数更小的 Dirichlet 前缀和/差分 算法，但是算法时间复杂度仍为 𝑂(𝑛 l o g⁡l o g⁡𝑛)O(n log⁡log⁡n)．

### 结果为积性函数的情形

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

ℎ(𝑝 𝑒)=𝑒∑𝑖=0 𝑓(𝑝 𝑖)𝑔(𝑝 𝑒−𝑖).h(p e)=∑i=0 e f(p i)g(p e−i).

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

∑𝑝∈𝐏, 𝑝≤𝑛⌊l o g 𝑝⁡𝑛⌋∑𝑒=1(𝑒+1)≤∑𝑝∈𝐏, 𝑝≤√𝑛⌊l o g 𝑝⁡𝑛⌋2+∑𝑝∈𝐏, √𝑛<𝑝≤𝑛 1≤√𝑛(l o g 2⁡𝑛)2+𝑛∈𝑂(𝑛).∑p∈P, p≤n∑e=1⌊log p⁡n⌋(e+1)≤∑p∈P, p≤n⌊log p⁡n⌋2+∑p∈P, n<p≤n 1≤n(log 2⁡n)2+n∈O(n).

因此，这一算法的总时间复杂度为 𝑂(𝑛)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
- Dirichlet 積と、数論関数の累積和 by maspy

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 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 协议之条款下提供，附加条款亦可能应用