狄利克雷卷积

Aleph_Drawer · 2023-12-21 17:22:27 · 算法·理论

对于两个数论函数 f(x) 与 g(x)，它们的狄利克雷卷积（Dirichlet Convolution）通常定义如下：

(f * g)(n) = \sum_{d \mid n} f(d) g(\dfrac nd) = \sum_{ab = n}f(a)g(b)

接下来来探讨这个卷积的一些性质。

先来定义一些函数，如下：

单位函数（单位元）：\varepsilon(x) := [x = 1]。
幂函数：\mathrm{id}_k(x) := x^k，当 k = 1 时为恒等函数，简记为 \mathrm{id}(x)，当 k = 0 时为常函数，简记为 \mathbf 1(x)，虽然用不到，但是额外声明 0^0 = 1 可能会方便一点。
约数和函数，定义为 \sigma_x(n) := \sum_{d \mid n} d^x，常将 \sigma_1(n) 简写为 \sigma(n)。
以及欧拉函数 \varphi(x)，定义为 \varphi(x) := \sum_{i = 1}^{x} [\gcd(x,i) = 1]。

上述四个均为积性函数。前面两个是完全积性函数。

狄利克雷卷积满足交换律结合律分配律。以及 f * h = g * h \Leftrightarrow f = g, h(1) \neq 0。

首先是两个积性函数的狄利克雷卷积也是积性函数。利用定义大胆证明即可。

然后是一些基本的定义结论：

(f * \mathbf 1)(n) = \sum_{d \mid n} f(d)

所以

(\mathrm {id}_k * \mathbf 1)(n) = \sum_{d \mid n} d^k = \sigma_k(n) \Rightarrow \mathrm{id}_k * \mathbf 1 = \sigma_k

然后来看这么一个式子

(\varphi * \mathbf 1)(n) = \sum_{d \mid n} \varphi(d)

令 n = p^m，那么原式就变成

\sum_{i = 0}^{m} \varphi(p^i) = 1 + \sum_{i = 1}^m (p^i - p^{i - 1}) = p^m = n

再令 n 为任意正整数，那么有唯一分解，显然 (\varphi * \mathbf 1) 是一个积性函数，那么如果令 n = \prod p_i^{c_i}，那么就有

(\varphi * \mathbf 1)(\prod_i p_i^{c_i}) = \prod_i(\varphi * \mathbf 1)(p_i^{c_i}) = \prod_i p_i^{c_i} = n

所以

\varphi * \mathbf 1 = \mathrm{id}

然后是 f * \varepsilon = f，还有 \mu * \mathbf 1 = \varepsilon 这个太显然了。

如果你把 \varepsilon 当成普通乘法运算中的 1，那么狄利克雷卷积的逆元就定义为，如果 f * g = \varepsilon，那么就称 g 是 f 的狄利克雷逆元。可以写成 f^{-1}。

这个有什么用呢？看看 \mathbf 1^{-1} 是什么？

(\mathbf 1 * \mathbf 1^{-1})(n) = [n = 1] \\ \sum_{d \mid n}\mathbf 1^{-1}(d) = [n = 1]

设成 g 吧。直接写有点难看。

\sum_{d \mid n} g(d) = [n = 1]

那么我们首先知道，g(1) = 1。

对于质数 p，你要有 g(p) = -1，因为你要让 g(1) + g(p) = 0。

那么对于 g(p^c), c \geq 2，你就不能让值等于除 0 以外的其他值了，以 n = 9 举例，此时 g(1) + g(3) + g(9) = 0，由于 g(1) + g(3) = 0，所以你 g(9)，只能为 0。

然后你要知道 g 是积性函数。

然后你会发现，g = \mu。我们上面做的，只是在证明我们在莫比乌斯反演中用到的特别多的一个性质。

这个也是有用的，比如说 \varphi * \mathbf 1 = \mathrm{id} \Rightarrow \varphi = \mathrm{id} * \mu。

不妨深入一点。尝试说明

f = g * 1 \Rightarrow g = \mu * f

这个就是莫比乌斯反演

f(n)= \sum_{d \mid n} g(n), g(n) = \sum_{d \mid n} \mu(d) f(\dfrac nd)

然后你发现第一个等式两边同时乘上 \mu 就可以得到

f * \mu = g * 1 * \mu \Rightarrow f * \mu = g * \varepsilon = g

就证明完了。

首先其实莫比乌斯反演这个东西是可以用狄利克雷卷积很好的去理解的。

然后这个东西对杜教筛也是非常有用的。

在一些数数题中可以用得到。