狄利克雷卷积与反演

狄利克雷卷积把两个数论函数合成为一个新的数论函数；
莫比乌斯反演则负责从因数求和中恢复原函数。

1 从整数乘法到函数乘法

算术基本定理把整数拆成质数幂，积性函数把函数值拆成各个质数幂上的局部贡献。狄利克雷卷积进一步在“因数分解”上定义数论函数之间的乘法。

本章主线：基本数论函数 → 狄利克雷卷积 → 单位元与逆元 → 常见卷积恒等式 → 莫比乌斯反演 → 构造卷积系数 → 消去 $\gcd$ 限制。

卷积与反演是后续互质计数、数论求和和杜教筛的共同语言。

---

2 基本数论函数

2.1 单位函数

单位函数 $\varepsilon$ 定义为

$$\varepsilon(n)= \begin{cases} 1, & n=1,\\ 0, & n>1. \end{cases}$$

它在狄利克雷卷积中扮演单位元的角色。

2.2 常数函数

常数函数 $1$ 定义为 $1(n)=1$。

这里的 $1$ 是一个数论函数，不是单位函数 $\varepsilon$。两者只有在 $n=1$ 时取值相同。

2.3 恒等函数

恒等函数 $\operatorname{id}$ 定义为 $\operatorname{id}(n)=n$。

更一般地，可以定义幂函数 $\operatorname{id}_k(n)=n^k$。

---

3 狄利克雷卷积

3.1 定义

对两个数论函数 $f,g$，它们的狄利克雷卷积定义为

$$(f*g)(n)=\sum_{d\mid n}f(d)g\left(\frac nd\right).$$

求和遍历 $n$ 的所有因数，并把 $n$ 拆成 $d\cdot(n/d)$。

例如

$$(1*1)(n)=\sum_{d\mid n}1=\tau(n),$$

因此因数个数函数满足 $\tau=1*1$。

类似地，

$$(\operatorname{id}*1)(n)=\sum_{d\mid n}d=\sigma(n),$$

所以因数和函数满足 $\sigma=\operatorname{id}*1$。

3.2 运算性质

狄利克雷卷积满足：

• 交换律：$f*g=g*f$；
• 结合律：$(f*g)*h=f*(g*h)$；
• 对函数加法的分配律：$f*(g+h)=f*g+f*h$；
• 单位元：$f*\varepsilon=f$。

这些性质允许我们像处理普通乘法一样变形卷积等式。

与代数结构的联系

全体数论函数在狄利克雷卷积下构成交换幺半群，但并不是每个函数都有卷积逆元。

参见：02_代数运算结构

3.3 卷积逆元

若存在数论函数 $g$ 满足 $f*g=\varepsilon$，则称 $g$ 是 $f$ 的狄利克雷逆元，记作 $f^{-1}$。

当函数值位于 $\mathbb Q,\mathbb R,\mathbb C$ 等域中时，$f$ 存在狄利克雷逆元，当且仅当 $f(1)\ne0$。

在模 $M$ 意义下，条件相应变为 $f(1)$ 在模 $M$ 下可逆。

因此，不能笼统地说“所有数论函数在卷积下构成群”；只有可逆的数论函数才构成群。

3.4 积性函数与卷积

若 $f,g$ 都是积性函数，则 $f*g$ 仍然是积性函数。

因此，卷积不仅保留数论函数的结构，也保留积性。研究卷积等式时，常常只需要研究质数幂上的取值。

---

4 常见卷积恒等式

4.1 莫比乌斯函数

莫比乌斯函数满足

$$\mu*1=\varepsilon.$$

展开后就是

$$\sum_{d\mid n}\mu(d)= \begin{cases} 1, & n=1,\\ 0, & n>1. \end{cases}$$

因此，$\mu$ 是常数函数 $1$ 的狄利克雷逆元。

这条恒等式最重要的作用，是把“最大公因数等于 $1$”转化为因数求和：

$$[\gcd(a,b)=1]=\sum_{d\mid\gcd(a,b)}\mu(d).$$

4.2 欧拉函数

欧拉函数满足

$$\varphi*1=\operatorname{id}.$$

展开后得到

$$\sum_{d\mid n}\varphi(d)=n.$$

由 $\mu*1=\varepsilon$，两边再卷积 $\mu$，还可以得到

$$\varphi=\operatorname{id}*\mu.$$

也就是

$$\varphi(n)=\sum_{d\mid n}d\,\mu\left(\frac nd\right) =n\sum_{d\mid n}\frac{\mu(d)}d.$$

4.3 因数函数

因数个数与因数和可以统一写成

$$\tau=1*1,\qquad \sigma=\operatorname{id}*1.$$

更一般地，$k$ 次因数和函数 $\sigma_k(n)=\displaystyle\sum_{d\mid n}d^k$ 满足

$$\sigma_k=\operatorname{id}_k*1.$$

4.4 Jordan 函数

定义

$$J_k=\operatorname{id}_k*\mu.$$

由 $\mu*1=\varepsilon$，可以得到

$$J_k*1=\operatorname{id}_k.$$

因此

$$n^k=\sum_{d\mid n}J_k(d).$$

当 $k=1$ 时，$J_1=\varphi$。Jordan 函数会自然出现在 $\gcd(i,j)^k$ 的求和中。

---

5 莫比乌斯反演

5.1 因数形式

若

$$F(n)=\sum_{d\mid n}f(d),$$

那么 $F=f*1$。

由于 $\mu*1=\varepsilon$，两边卷积 $\mu$，可以得到

$$f=F*\mu.$$

展开后就是莫比乌斯反演公式：

$$f(n)=\sum_{d\mid n}\mu(d)F\left(\frac nd\right) =\sum_{d\mid n}\mu\left(\frac nd\right)F(d).$$

它的作用可以概括为：

因数求和负责累积，莫比乌斯函数负责把累积贡献重新拆开。

5.2 倍数形式

在只考虑 $1$ 到 $N$ 的有限范围时，若

$$F(n)=\sum_{\substack{n\mid d\\d\le N}}f(d),$$

那么

$$f(n)=\sum_{\substack{n\mid d\\d\le N}} \mu\left(\frac dn\right)F(d).$$

因数形式沿着因数向下求和，倍数形式沿着倍数向上求和，两者本质上是同一个反演关系。

5.3 精确计数与累积计数

设 $f(d)$ 表示某种对象中“参数恰好等于 $d$”的数量，$F(d)$ 表示“参数是 $d$ 的倍数”的数量。

那么通常有

$$F(d)=\sum_{d\mid k}f(k).$$

此时可以用倍数形式的莫比乌斯反演恢复精确数量。

这一视角在 $\gcd$ 计数中尤其常见：

• 精确条件是 $\gcd(i,j)=d$；
• 累积条件是 $d\mid\gcd(i,j)$；
• 后者等价于 $d\mid i$ 且 $d\mid j$，更容易统计。

---

6 构造卷积系数

卷积在题目中的核心作用通常不是“计算两个函数的卷积”，而是寻找一个权函数，把目标函数改写为因数和。

设题目中出现 $f(\gcd(i,j))$。令

$$g=f*\mu.$$

由于 $g*1=f$，对任意正整数 $x$ 都有

$$f(x)=\sum_{d\mid x}g(d).$$

代入 $x=\gcd(i,j)$：

$$f(\gcd(i,j)) =\sum_{d\mid\gcd(i,j)}g(d) =\sum_{\substack{d\mid i\\d\mid j}}g(d).$$

交换求和顺序后得到统一公式：

$$\sum_{i=1}^{n}\sum_{j=1}^{m}f(\gcd(i,j)) = \sum_{d=1}^{\min(n,m)} g(d) \left\lfloor\frac nd\right\rfloor \left\lfloor\frac md\right\rfloor,$$

其中 $g=f*\mu$。

这条公式把二维的 $\gcd$ 条件转化为了一个一维数论函数的前缀和问题。

6.1 互质数对

取 $f=\varepsilon$，则 $g=\varepsilon*\mu=\mu$。

因此

$$\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=1] = \sum_{d=1}^{\min(n,m)} \mu(d) \left\lfloor\frac nd\right\rfloor \left\lfloor\frac md\right\rfloor.$$

6.2 最大公因数等于 $k$

若 $\gcd(i,j)=k$，则 $k\mid i,j$，并且

$$\gcd\left(\frac ik,\frac jk\right)=1.$$

所以只需要把范围缩小为 $\lfloor n/k\rfloor$ 与 $\lfloor m/k\rfloor$，再计算互质数对。

对于矩形区间 $[a,b]\times[c,d]$，继续使用二维前缀容斥：

$$F(b,d)-F(a-1,d)-F(b,c-1)+F(a-1,c-1).$$

6.3 最大公因数求和

取 $f=\operatorname{id}$，则 $g=\operatorname{id}*\mu=\varphi$。

因此

$$\sum_{i=1}^{n}\sum_{j=1}^{m}\gcd(i,j) = \sum_{d=1}^{\min(n,m)} \varphi(d) \left\lfloor\frac nd\right\rfloor \left\lfloor\frac md\right\rfloor.$$

这正是恒等式 $\operatorname{id}=\varphi*1$ 在二维求和中的应用。

6.4 最大公因数的 $k$ 次幂

取 $f=\operatorname{id}_k$，则 $g=J_k=\operatorname{id}_k*\mu$。

因此

$$\sum_{i=1}^{n}\sum_{j=1}^{m}\gcd(i,j)^k = \sum_{d=1}^{\min(n,m)} J_k(d) \left\lfloor\frac nd\right\rfloor \left\lfloor\frac md\right\rfloor.$$

$J_k$ 是积性函数，可以在线性筛中递推。

6.5 最大公因数为质数

定义质数指示函数

$$P(n)=[n\text{ 是质数}].$$

令 $g=P*\mu$，则

$$g(T)=\sum_{p\mid T}\mu\left(\frac Tp\right),$$

其中 $p$ 遍历 $T$ 的质因数。

于是

$$\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)\text{ 是质数}] = \sum_{T=1}^{\min(n,m)} g(T) \left\lfloor\frac nT\right\rfloor \left\lfloor\frac mT\right\rfloor.$$

这里的关键不是背诵 $g$ 的形式，而是先确定目标函数 $P$，再统一计算 $P*\mu$。

---

7 更复杂的权值转化

并非所有题目都直接写成 $f(\gcd(i,j))$，但仍然可以沿用同一思路：

1. 把目标表达式改写成因数求和；
2. 通过卷积或反演找到一维权函数；
3. 交换求和顺序；
4. 把二维枚举转化为若干个整除商与前缀和。

7.1 最小公倍数求和

利用 $\operatorname{lcm}(i,j)=ij/\gcd(i,j)$，可以推导出

$$\sum_{i=1}^{n}\sum_{j=1}^{m}\operatorname{lcm}(i,j) = \sum_{T=1}^{\min(n,m)} h(T) S\left(\left\lfloor\frac nT\right\rfloor\right) S\left(\left\lfloor\frac mT\right\rfloor\right),$$

其中 $S(x)=x(x+1)/2$，并且

$$h(T)=T\sum_{d\mid T}\mu(d)d.$$

7.2 带乘积权值的 $\gcd$ 求和

对于

$$\sum_{i=1}^{n}\sum_{j=1}^{m}ij\gcd(i,j),$$

最终需要的权函数为 $d^2\varphi(d)$：

$$\sum_{d=1}^{\min(n,m)} d^2\varphi(d) S\left(\left\lfloor\frac nd\right\rfloor\right) S\left(\left\lfloor\frac md\right\rfloor\right).$$

7.3 因数个数求和

对于

$$\sum_{i=1}^{n}\sum_{j=1}^{m}\tau(ij),$$

可以转化为

$$\sum_{d=1}^{\min(n,m)} \mu(d) F\left(\left\lfloor\frac nd\right\rfloor\right) F\left(\left\lfloor\frac md\right\rfloor\right),$$

其中

$$F(x)=\sum_{i=1}^{x}\left\lfloor\frac xi\right\rfloor =\sum_{i=1}^{x}\tau(i).$$

这些公式的计算都依赖数论函数前缀和与整除分块，具体实现放在 06_数论求和 中展开。

---

8 计算卷积与反演

直接按照定义计算 $1$ 到 $N$ 的卷积，可以枚举因数与对应倍数。

▶

狄利克雷卷积

ll f[maxn], g[maxn], h[maxn];

// h = f * g
void conv( int N ) {
    fill( h, h + N + 1, 0 );

    for( int d = 1; d <= N; ++ d ) {
        for( int k = 1; d * k <= N; ++ k ) {
            h[d * k] += f[d] * g[k];
        }
    }
}

总枚举次数为 $\displaystyle\sum_{d=1}^{N}\lfloor N/d\rfloor$，时间复杂度为 $O(N\log N)$。

若已知 $F=f*1$，并已经预处理莫比乌斯函数，也可以直接计算 $f=F*\mu$。

▶

莫比乌斯反演

ll F[maxn], f[maxn];
int mu[maxn];

// f = F * mu
void inv( int N ) {
    fill( f, f + N + 1, 0 );

    for( int d = 1; d <= N; ++ d ) {
        for( int k = 1; d * k <= N; ++ k ) {
            f[d * k] += 1LL * mu[d] * F[k];
        }
    }
}

若题目要求取模，只需要在累加过程中按题目模数处理。莫比乌斯函数的线性筛参见 03_数论函数与线性筛。

---

9 与后续内容的联系

• $\mu*1=\varepsilon$ 用于消去互质与最大公因数限制；
• $\varphi*1=\operatorname{id}$ 既能推导 $\gcd$ 求和，也是杜教筛的基础；
• $J_k=\operatorname{id}_k*\mu$ 统一描述 $\gcd^k$ 求和中的权函数；
• 更复杂的权值题本质上仍是在寻找合适的卷积系数；
• 卷积变形后的求和通常需要整除分块、前缀和或杜教筛计算。

相关内容：

• 03_数论函数与线性筛
• 06_数论求和