狄利克雷卷积：数论函数的“乘法”

把函数“卷”起来，就像分糖果一样

我们熟悉加法和乘法，但你知道吗？函数之间也能进行运算。狄利克雷卷积就是一种特殊的“乘法”，它把两个数论函数 $f$ 和 $g$ 组合成一个新函数 $f * g$ 。定义如下：

(f * g)(n) = \sum_{d|n} f(d) \cdot g\left(\frac{n}{d}\right)

这个公式的意思是：对于每个正整数 $n$ ，我们枚举它的所有正因子 $d$ ，把 $f(d)$ 和 $g(n/d)$ 相乘，然后把所有乘积加起来。

你可以这样想象：老师给全班同学分糖果，糖果总数是 $n$ 颗。老师先让每个小组长（对应因子 $d$ ）按某种规则领走 $f(d)$ 颗糖，然后剩下的糖果（ $n/d$ ）再按另一种规则分给组员 $g(n/d)$ 。最后把所有小组的得分加起来，就是全班的总分。这就是“卷”在一起——一个函数从因子的角度贡献，另一个函数从商的角度贡献。

为什么要学这个？——让复杂求和变简单

狄利克雷卷积是数论中的“乘法”。很多重要的数论恒等式都可以用卷积简洁地表达。比如：

恒等函数 $I(n)=1$ 与任何函数 $f$ 的卷积： $(f * I)(n) = \sum_{d|n} f(d)$ ，这正是因子求和！
若 $\mu$ 是莫比乌斯函数，则 $\mu * I = \varepsilon$ ，其中 $\varepsilon(n)=[n=1]$ （单位函数）。
若 $\varphi$ 是欧拉函数，则 $\varphi * I = id$ ，其中 $id(n)=n$ 。

这些关系让我们能轻松地在不同函数之间转换，就像用乘法分配律化简代数式一样。

卷积的性质——乘法的“好习惯”

狄利克雷卷积满足：

交换律： $f * g = g * f$ （因为因子对 $(d, n/d)$ 对称，就像交换两个乘数的位置结果不变）。
结合律： $(f * g) * h = f * (g * h)$ （先卷哪两个都行）。
单位元： $\varepsilon * f = f$ ，其中 $\varepsilon(n) = \begin{cases} 1 & n=1 \\ 0 & n>1 \end{cases}$ （就像乘法中的1，任何函数卷上它都不变）。
积性函数的卷积仍是积性函数：如果 $f$ 和 $g$ 都是积性函数，那么 $f * g$ 也是积性函数。这个性质超级有用，后面会用到。

假设你在学校小卖部排队。队伍的长度 $n$ 是总人数。每个人（ $d$ ）手上有一种零食数量 $f(d)$ ，他后面跟的人（ $n/d$ ）有另一种零食数量 $g(n/d)$ 。那么整个队伍的总零食量就是 $(f * g)(n)$ 。如果队伍只有1个人（ $n=1$ ），那么只有 $d=1$ 一种分法，结果就是 $f(1) \cdot g(1)$ 。如果队伍有6个人，可以分成1人和6人、2人和3人、3人和2人、6人和1人等多种方式，每种方式的两段零食数相乘再求和。

新手容易犯的错误

忘记 $n=1$ 的情况：当 $n=1$ 时，只有因子 $d=1$ ，求和只有一项 $f(1) \cdot g(1)$ 。很多同学会误以为求和为空，或者漏掉。
数组下标从0还是1开始：数论函数通常从 $n=1$ 开始有意义。编程实现时，数组下标0可以空着，或者把0也当作索引，但要注意 $f[0]$ 一般不用。常见错误是循环从0开始，导致访问了无效数据。
循环边界写错：枚举因子对时，双重循环的终止条件要小心。例如 for d in range(1, n+1): for k in range(1, n//d + 1): 确保 $d \cdot k \le n$ 。如果写成 k <= n 就会越界或重复计算。
数据类型溢出：卷积结果可能很大，比如 $id * id$ 的 $n=100$ 时结果已经超过 int 范围。建议用 long long 或 Python 的 int。

例子：计算一些简单的卷积

例1：设 $f(n)=n$ ， $g(n)=1$ ，则 $(f*g)(n) = \sum_{d|n} d \cdot 1 = \sigma(n)$ （除数之和函数）。所以 $id * 1 = \sigma$ 。

例2：设 $f(n)=\mu(n)$ ， $g(n)=1$ ，则 $(\mu*1)(n) = \sum_{d|n} \mu(d)$ 。我们已经知道这个和等于 $[n=1]$ ，即 $\varepsilon$ 。所以 $\mu * 1 = \varepsilon$ 。

例3：设 $f(n)=\varphi(n)$ ， $g(n)=1$ ，则 $(\varphi*1)(n) = \sum_{d|n} \varphi(d)$ 。可以证明这个和等于 $n$ （因为欧拉函数的性质）。所以 $\varphi * 1 = id$ 。

这些例子展示了卷积如何把看似不同的函数联系起来。

编程实现：亲手算一算

给定两个函数 $f$ 和 $g$ ，我们可以用数组表示它们（下标从1开始）。对于每个 $n$ ，枚举所有因子 $d$ 即可。复杂度是 $O(n \log n)$ （因为因子求和的总次数是 $n(1+1/2+1/3+...) \approx n \log n$ ）。

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(n \log n)$ （调和级数）。

卷积与积性函数

如果 $f$ 和 $g$ 都是积性函数（即对于互质的 $a,b$ 有 $f(ab)=f(a)f(b)$ 且 $g(ab)=g(a)g(b)$ ），那么它们的卷积 $h = f * g$ 也是积性函数。这一性质可以用来证明许多恒等式。例如，因为 $\mu$ 和 $1$ 都是积性的，所以它们的卷积 $\varepsilon$ 也是积性的（实际上 $\varepsilon$ 是完全积性的）。

利用卷积，莫比乌斯反演可以写成：若 $F = f * 1$ ，则 $f = F * \mu$ 。这将在下一个知识点详细讲解。

小结

狄利克雷卷积是数论中的核心操作，它将因子求和统一为一种乘法。掌握卷积的语言，你就能把复杂的求和公式变得简洁优美。今后见到 $\sum_{d|n} f(d) g(n/d)$ ，你就能认出这是一个卷积。

思考：试用卷积证明 $\varphi * 1 = id$ 。（提示：先证明对质数幂成立，再利用积性。）

狄利克雷卷积