狄利克雷卷积
把函数“卷”起来,就像分糖果一样
我们熟悉加法和乘法,但你知道吗?函数之间也能进行运算。狄利克雷卷积就是一种特殊的“乘法”,它把两个数论函数 fff 和 ggg 组合成一个新函数 f∗gf * gf∗g。定义如下:
(f∗g)(n)=∑d∣nf(d)⋅g(nd)(f * g)(n) = \sum_{d|n} f(d) \cdot g\left(\frac{n}{d}\right)(f∗g)(n)=d∣n∑f(d)⋅g(dn)
这个公式的意思是:对于每个正整数 nnn,我们枚举它的所有正因子 ddd,把 f(d)f(d)f(d) 和 g(n/d)g(n/d)g(n/d) 相乘,然后把所有乘积加起来。
你可以这样想象:老师给全班同学分糖果,糖果总数是 nnn 颗。老师先让每个小组长(对应因子 ddd)按某种规则领走 f(d)f(d)f(d) 颗糖,然后剩下的糖果(n/dn/dn/d)再按另一种规则分给组员 g(n/d)g(n/d)g(n/d)。最后把所有小组的得分加起来,就是全班的总分。这就是“卷”在一起——一个函数从因子的角度贡献,另一个函数从商的角度贡献。
为什么要学这个?——让复杂求和变简单
狄利克雷卷积是数论中的“乘法”。很多重要的数论恒等式都可以用卷积简洁地表达。比如:
- 恒等函数 I(n)=1I(n)=1I(n)=1 与任何函数 fff 的卷积:(f∗I)(n)=∑d∣nf(d)(f * I)(n) = \sum_{d|n} f(d)(f∗I)(n)=∑d∣nf(d),这正是因子求和!
- 若 μ\muμ 是莫比乌斯函数,则 μ∗I=ε\mu * I = \varepsilonμ∗I=ε,其中 ε(n)=[n=1]\varepsilon(n)=[n=1]ε(n)=[n=1](单位函数)。
- 若 φ\varphiφ 是欧拉函数,则 φ∗I=id\varphi * I = idφ∗I=id,其中 id(n)=n id(n)=nid(n)=n。
这些关系让我们能轻松地在不同函数之间转换,就像用乘法分配律化简代数式一样。
卷积的性质——乘法的“好习惯”
狄利克雷卷积满足:
- 交换律:f∗g=g∗ff * g = g * ff∗g=g∗f(因为因子对 (d,n/d)(d, n/d)(d,n/d) 对称,就像交换两个乘数的位置结果不变)。
- 结合律:(f∗g)∗h=f∗(g∗h)(f * g) * h = f * (g * h)(f∗g)∗h=f∗(g∗h)(先卷哪两个都行)。
- 单位元:ε∗f=f\varepsilon * f = fε∗f=f,其中 ε(n)={1n=10n>1\varepsilon(n) = \begin{cases} 1 & n=1 \ 0 & n>1 \end{cases}ε(n)={10n=1n>1(就像乘法中的1,任何函数卷上它都不变)。
- 积性函数的卷积仍是积性函数:如果 fff 和 ggg 都是积性函数,那么 f∗gf * gf∗g 也是积性函数。这个性质超级有用,后面会用到。
生活中的比喻:排队领零食
假设你在学校小卖部排队。队伍的长度 nnn 是总人数。每个人(ddd)手上有一种零食数量 f(d)f(d)f(d),他后面跟的人(n/dn/dn/d)有另一种零食数量 g(n/d)g(n/d)g(n/d)。那么整个队伍的总零食量就是 (f∗g)(n)(f * g)(n)(f∗g)(n)。如果队伍只有1个人(n=1n=1n=1),那么只有 d=1d=1d=1 一种分法,结果就是 f(1)⋅g(1)f(1) \cdot g(1)f(1)⋅g(1)。如果队伍有6个人,可以分成1人和6人、2人和3人、3人和2人、6人和1人等多种方式,每种方式的两段零食数相乘再求和。
新手容易犯的错误
- 忘记 n=1n=1n=1 的情况:当 n=1n=1n=1 时,只有因子 d=1d=1d=1,求和只有一项 f(1)⋅g(1)f(1) \cdot g(1)f(1)⋅g(1)。很多同学会误以为求和为空,或者漏掉。
- 数组下标从0还是1开始:数论函数通常从 n=1n=1n=1 开始有意义。编程实现时,数组下标0可以空着,或者把0也当作索引,但要注意 f[0]f[0]f[0] 一般不用。常见错误是循环从0开始,导致访问了无效数据。
- 循环边界写错:枚举因子对时,双重循环的终止条件要小心。例如
for d in range(1, n+1): for k in range(1, n//d + 1):确保 d⋅k≤nd \cdot k \le nd⋅k≤n。如果写成k <= n就会越界或重复计算。 - 数据类型溢出:卷积结果可能很大,比如 id∗idid * idid∗id 的 n=100n=100n=100 时结果已经超过 int 范围。建议用
long long或 Python 的 int。
例子:计算一些简单的卷积
例1:设 f(n)=nf(n)=nf(n)=n,g(n)=1g(n)=1g(n)=1,则 (f∗g)(n)=∑d∣nd⋅1=σ(n)(f*g)(n) = \sum_{d|n} d \cdot 1 = \sigma(n)(f∗g)(n)=∑d∣nd⋅1=σ(n)(除数之和函数)。所以 id∗1=σid * 1 = \sigmaid∗1=σ。
例2:设 f(n)=μ(n)f(n)=\mu(n)f(n)=μ(n),g(n)=1g(n)=1g(n)=1,则 (μ∗1)(n)=∑d∣nμ(d)(\mu*1)(n) = \sum_{d|n} \mu(d)(μ∗1)(n)=∑d∣nμ(d)。我们已经知道这个和等于 [n=1][n=1][n=1],即 ε\varepsilonε。所以 μ∗1=ε\mu * 1 = \varepsilonμ∗1=ε。
例3:设 f(n)=φ(n)f(n)=\varphi(n)f(n)=φ(n),g(n)=1g(n)=1g(n)=1,则 (φ∗1)(n)=∑d∣nφ(d)(\varphi*1)(n) = \sum_{d|n} \varphi(d)(φ∗1)(n)=∑d∣nφ(d)。可以证明这个和等于 nnn(因为欧拉函数的性质)。所以 φ∗1=id\varphi * 1 = idφ∗1=id。
这些例子展示了卷积如何把看似不同的函数联系起来。
编程实现:亲手算一算
给定两个函数 fff 和 ggg,我们可以用数组表示它们(下标从1开始)。对于每个 nnn,枚举所有因子 ddd 即可。复杂度是 O(nlogn)O(n \log n)O(nlogn)(因为因子求和的总次数是 n(1+1/2+1/3+...)≈nlognn(1+1/2+1/3+...) \approx n \log nn(1+1/2+1/3+...)≈nlogn)。
C++ 实现
#include <iostream>
#include <vector>
using namespace std;
// 计算 f * g 的前 n 项,结果存入 h[1..n]
// f, g 是长度为 n+1 的数组(下标从0开始,但只使用1..n)
void dirichlet_convolution(const vector<long long>& f, const vector<long long>& g, vector<long long>& h, int n) {
h.assign(n + 1, 0); // 初始化结果数组全为0
// 枚举所有可能的 d 和 k 使得 d*k <= n
for (int d = 1; d <= n; d++) { // d 是第一个函数的自变量
for (int k = 1; d * k <= n; k++) { // k 是第二个函数的自变量
// 对于每个因子对 (d, k),贡献到乘积 d*k 的位置
h[d * k] += f[d] * g[k];
}
}
}
int main() {
const int N = 10; // 计算前10项
vector<long long> f(N + 1), g(N + 1), h; // 定义三个数组,f和g长度为N+1
for (int i = 1; i <= N; i++) {
f[i] = i; // id 函数:f(n)=n
g[i] = 1; // 常函数1:g(n)=1
}
dirichlet_convolution(f, g, h, N);
cout << "id * 1 的前10项:" << endl;
for (int i = 1; i <= N; i++) {
cout << "h(" << i << ") = " << h[i] << endl;
}
// 结果应该等于除数之和函数 σ(n) = 所有因子的和
return 0;
}
Python 实现
def dirichlet_convolution(f, g, n):
"""
计算 f * g 的前 n 项,返回列表 h[1..n]
f, g 是索引从1开始的列表(长度至少 n+1)
"""
h = [0] * (n + 1) # 初始化结果列表,索引0占位
for d in range(1, n + 1): # d 从1到n
for k in range(1, n // d + 1): # k 从1到n//d,保证 d*k <= n
h[d * k] += f[d] * g[k] # 累加贡献
return h
# 示例
N = 10
f = [0] + [i for i in range(1, N + 1)] # id 函数:f[n]=n
g = [0] + [1] * N # 常函数1:g[n]=1
h = dirichlet_convolution(f, g, N)
print("id * 1 的前10项:")
for i in range(1, N + 1):
print(f"h({i}) = {h[i]}")
注意:上面代码中,双重循环的顺序是枚举 d 然后枚举 k。这等价于枚举所有因子对,计算复杂度为 O(nlogn)O(n \log n)O(nlogn)(调和级数)。
卷积与积性函数
如果 fff 和 ggg 都是积性函数(即对于互质的 a,ba,ba,b 有 f(ab)=f(a)f(b)f(ab)=f(a)f(b)f(ab)=f(a)f(b) 且 g(ab)=g(a)g(b)g(ab)=g(a)g(b)g(ab)=g(a)g(b)),那么它们的卷积 h=f∗gh = f * gh=f∗g 也是积性函数。这一性质可以用来证明许多恒等式。例如,因为 μ\muμ 和 111 都是积性的,所以它们的卷积 ε\varepsilonε 也是积性的(实际上 ε\varepsilonε 是完全积性的)。
利用卷积,莫比乌斯反演可以写成:若 F=f∗1F = f * 1F=f∗1,则 f=F∗μf = F * \muf=F∗μ。这将在下一个知识点详细讲解。
小结
狄利克雷卷积是数论中的核心操作,它将因子求和统一为一种乘法。掌握卷积的语言,你就能把复杂的求和公式变得简洁优美。今后见到 ∑d∣nf(d)g(n/d)\sum_{d|n} f(d) g(n/d)∑d∣nf(d)g(n/d),你就能认出这是一个卷积。
思考:试用卷积证明 φ∗1=id\varphi * 1 = idφ∗1=id。(提示:先证明对质数幂成立,再利用积性。)
相关指引
- 想要更深入地理解卷积如何简化数论问题?请学习 莫比乌斯反演。
- 想知道哪些函数是积性的?请查看 积性函数 的知识点。
- 如果对因子求和还有疑问,回顾 因数与倍数 的基础知识。