莫比乌斯反演

luoguhandongheng · 2025-10-08 22:08:22 · 算法·理论

广告。

本文的重点不是处理式子，只是希望带给你一种莫反的新理解。

问题

像各种反演模型一样，莫比乌斯反演是一种代替容斥的强大工具。 它解决的问题如下：如果已知 f_k = \sum_{d | k}g_d，那么 g_k = \sum_{d | k}f({k \over d})\mu(d)。

莫比乌斯函数是容斥系数

正整数是一个以质数为基底的高维空间。对于 n = \prod p_i^{\alpha_i}，我们认为它的坐标是 (\alpha_1, \alpha_2, \cdots, \alpha_i, \cdots)。可以发现，上述 f_k 的定义就是此意义下的高维前缀和，现在，我们想根据高维前缀和求出原数组。

类比二维的情况，a_{i, j} = sum_{i, j} - sum_{i - 1, j} - sum_{i, j - 1} + sum_{i - 1, j - 1}，稍微手玩一下三维的，我们发现对于维度是 n 的情况来说，g_{(\alpha_1, \alpha_2, \cdots, \alpha_n)} = \sum_{S \subset \{1, 2, \cdots, n \} } (-1)^{|S|} f_{(\alpha_1 - [1 \in S], \cdots, \alpha_{i} - [i \in S], \cdots, \alpha_n - [n \in S])}。证明由容斥原理易得。

转化成整除式的表达，g_k = \sum_{d | k}f({k \over d})\mu(d)，这个 d 就类比上面的 S，也就是挑一些维度减去 1。也就是说，如果 d 有 t 个本质不同的质因子，那么这个就是容斥系数 (-1)^t。但到这就完了吗？如果 \exists p, p^2 | d 那也就意味着，我们至少挑了一些维度把这一维的坐标减去了 2，根据上面的式子，减 2 对于最终答案是没有任何贡献的。因此这种 d 的系数就应该是 0。

整理一下：

这就是莫比乌斯函数的定义了。

一些性质

1. 莫比乌斯函数是积性函数

容易验证。