莫比乌斯反演定理：从数论基石到算法利器

在数学的浩瀚星空中，莫比乌斯反演定理无疑是一颗璀璨而神秘的星辰。它起源于 19 世纪德国数学家奥古斯特·费迪南德·莫比乌斯（August Ferdinand Möbius）的研究工作，最初是为了处理数论中的求和问题而诞生的。然而，随着计算机科学的发展，尤其是算法竞赛领域的兴起，这一原本属于纯数学范畴的理论，逐渐演变成了程序员手中一把锋利的“手术刀”，专门用来切割那些看似复杂无比的整除、公约数以及容斥原理相关的问题。

许多初学者在面对涉及 gcd(a, b) 的求和公式时，往往感到束手无策，认为需要遍历所有可能的数对，导致时间复杂度爆炸。但实际上，莫比乌斯反演提供了一种优雅的视角转换：它将“直接计数”的困难问题，转化为“通过性质剔除多余项”的巧妙过程。这种思维方式不仅体现了数学的对称美，更是连接抽象代数与具体算法实现的桥梁。本文将深入剖析莫比乌斯反演定理的底层逻辑，通过详实的推导、丰富的示例以及实际代码，为您构建一个完整的知识体系。

要理解莫比乌斯反演，首先必须彻底掌握其核心载体——莫比乌斯函数（Möbius function），通常记作 μ(n)。这是一个定义在正整数集上的数论函数，它的取值完全取决于该整数的质因数分解结构。

最重要的恒等式

在所有关于 莫比乌斯函数 的性质中，最著名且最具威力的是以下恒等式：

Σ_{d|n} μ(d) = [n = 1]
        

这里的 [P] 是艾弗森括号（Iverson Bracket），当命题 P 为真时值为 1，否则为 0。

• 当 n = 1 时，唯一的约数是 1，所以 μ(1) = 1，等式成立。
• 当 n > 1 时，设 n = p₁^a₁ p₂^a₂ ... pₖ^aₖ。根据定义，任何包含平方因子的约数贡献为 0。因此我们只需要考虑由不同素数组成的约数。这些约数恰好对应于集合 {p₁, p₂, ..., pₖ} 的所有子集。
  对于大小为 k 的子集，其对应的 μ 值为 (-1)^k。根据二项式定理，所有子集的 μ 值之和为：
  C(k,0)(-1)^0 + C(k,1)(-1)^1 + ... + C(k,k)(-1)^k = (1-1)^k = 0。
  因此，当 n > 1 时，和为 0。

这个恒等式就是莫比乌斯反演的灵魂所在，它告诉我们如何通过加权求和来“筛选”出特定的数值（通常是 1）。

莫比乌斯反演定理主要有两种表现形式，分别适用于不同的场景。虽然它们的数学背景略有不同，但核心思想是一致的：利用逆运算恢复原函数。

Σ_{d|n} μ(d) F(n/d)
= Σ_{d|n} μ(d) [ Σ_{k|(n/d)} f(k) ]
令 n/d = m，则 d = n/m。当 d 遍历 n 的约数时，m 也遍历 n 的约数。
= Σ_{m|n} Σ_{k|m} μ(n/m) f(k)
交换求和顺序，先枚举 k，再枚举 m（m 必须是 k 的倍数且是 n 的约数）：
= Σ_{k|n} f(k) [ Σ_{j|(n/k)} μ(j) ]   (令 j = n/(mk) ? 不，令 m = kj，则 j|(n/k))
内部求和 Σ_{j|(n/k)} μ(j) 正好是 [n/k = 1]，即只有当 k=n 时为 1，其余为 0。
= f(n)  1 = f(n)
得证。
                

μ(x, x) = 1
μ(x, y) = - Σ_{x ≤ z < y} μ(x, z)   (当 x < y)
μ(x, y) = 0                      (当 x ≰ y)
                

掌握了理论之后，我们来看看莫比乌斯反演在实际应用中是如何发挥作用的。除了基础的数论题，它在容斥原理、组合数学甚至图论中都有深刻的体现。

1. 容斥原理的通用化

很多读者可能听说过容斥原理（Inclusion-Exclusion Principle），用于计算多个集合的并集大小。其实，莫比乌斯反演可以看作是容斥原理在任意偏序集上的推广。

2. 经典数论函数应用

在数论中，莫比乌斯反演常被用来求解各种算术函数的和。以下是几个典型例子：

• 欧拉函数 φ(n)：我们知道 Σ_{d|n} φ(d) = n。利用反演，可以直接得到 φ(n) = Σ_{d|n} μ(d) (n/d)。这为我们提供了一种通过 μ 函数计算 φ 的方法。
• 约数个数函数 d(n)：若 D(n) = Σ_{d|n} 1 = d(n)，这本身就是反演的结果。如果我们知道某个函数的约数和，想求原函数，就可以用反演。
• 最大公约数求和：这是最常见的题型。例如求 Σ_{i=1}^n Σ_{j=1}^m gcd(i, j)。通过枚举 g = gcd(i, j)，将问题转化为 Σ g count(gcd(i,j)=g)，再利用 μ 函数将 count 转化为前缀和形式。

在计算机领域，莫比乌斯反演的价值主要体现在优化算法复杂度上。下面我们通过一个经典的HDU 1695 / GCD 问题模型来演示其威力。

问题描述

给定整数 n, m, k，求有多少对 (x, y) 满足 1 ≤ x ≤ n, 1 ≤ y ≤ m 且 gcd(x, y) = k。

解题思路

1. 转化问题：
   gcd(x, y) = k 等价于 gcd(x/k, y/k) = 1。
   令 x' = x/k, y' = y/k，则问题转化为求 1 ≤ x' ≤ n/k, 1 ≤ y' ≤ m/k 且 gcd(x', y') = 1 的对数。
   不妨设 N = n/k, M = m/k，且 N ≤ M。我们需要计算：
   Ans = Σ_{i=1}^N Σ_{j=1}^M [gcd(i, j) = 1]
2. 引入莫比乌斯函数：
   利用恒等式 [n=1] = Σ_{d|n} μ(d)，将条件 [gcd(i, j) = 1] 替换：
   Ans = Σ_{i=1}^N Σ_{j=1}^M Σ_{d|gcd(i, j)} μ(d)
3. 交换求和顺序：
   d 必须同时整除 i 和 j，即 d|i 且 d|j。我们先枚举 d：
   Ans = Σ_{d=1}^N μ(d) Σ_{i=1, d|i}^N Σ_{j=1, d|j}^M 1
   内部求和分别是 floor(N/d) 和 floor(M/d)。
   Ans = Σ_{d=1}^N μ(d) floor(N/d) floor(M/d)
4. 整除分块优化：
   如果直接计算，复杂度为 O(N)。但如果 N, M 很大（如 10^5），单次查询没问题。如果是多组查询（如 T=10000），则需要进一步优化。
   注意到 floor(N/d) 和 floor(M/d) 的值在一段区间内是相同的。我们可以使用整除分块（数论分块）技术，将复杂度降为 O(√N)。
   为了支持快速查询 μ(d) 的前缀和，我们需要预处理 μ 函数及其前缀和数组 sumMu[]。

代码实现（C++ 伪代码）

// 预处理莫比乌斯函数
const int MAXN = 100005;
int mu[MAXN], prime[MAXN], cnt;
bool vis[MAXN];
long long sumMu[MAXN];
void sieve() {
    mu[1] = 1;
    for (int i = 2; i < MAXN; i++) {
        if (!vis[i]) {
            prime[++cnt] = i;
            mu[i] = -1;
        }
        for (int j = 1; j <= cnt && i  prime[j] < MAXN; j++) {
            vis[i  prime[j]] = true;
            if (i % prime[j] == 0) {
                mu[i  prime[j]] = 0;
                break;
            } else {
                mu[i  prime[j]] = -mu[i];
            }
        }
    }
    // 计算前缀和
    for (int i = 1; i < MAXN; i++) sumMu[i] = sumMu[i-1] + mu[i];
}
// 求解函数
long long solve(int n, int m) {
    if (n > m) swap(n, m);
    long long ans = 0;
    for (int l = 1, r; l <= n; l = r + 1) {
        r = min(n / (n / l), m / (m / l));
        ans += (sumMu[r] - sumMu[l - 1])  (long long)(n / l)  (m / l);
    }
    return ans;
}
        

这段代码展示了如何将一个看似需要 O(NM) 的暴力枚举，通过莫比乌斯反演和整除分块优化到接近线性的效率。这就是莫比乌斯反演在算法设计中的核心价值。

莫比乌斯反演定理不仅是数论中的一颗明珠，更是连接数学理论与计算机科学实践的重要纽带。从最初的数论研究，到如今算法竞赛中的常客，它证明了抽象数学的强大生命力。

通过本文的学习，您应该已经掌握了：

• 莫比乌斯函数的定义、性质及其最重要的恒等式。
• 莫比乌斯反演的两种形式及其推导过程。
• 如何利用莫比乌斯反演解决 GCD 求和等经典问题。
• 结合整除分块和线性筛的优化技巧。

希望这篇文章能帮助您建立起对莫比乌斯反演的深刻理解。如果您在深入学习过程中遇到新的问题，欢迎继续探索狄利克雷卷积、杜教筛等更高级的话题。数学的世界广阔无垠，愿您在探索的道路上不断发现新的惊喜！