莫比乌斯反演公式详解：从因子求和还原真相

1. 反演：一种“解方程”的思想

想象你有一个秘密数列 $f(n)$ ，但你不知道它。你只知道另一个数列 $F(n) = \sum_{d|n} f(d)$ ，即每个数的所有因子对应的 f 值之和。那么，你能从 F 反推出 f 吗？莫比乌斯反演给出了答案：

莫比乌斯反演公式：如果对于所有正整数 $n$ ，有

F(n) = \sum_{d|n} f(d)

那么

f(n) = \sum_{d|n} \mu(d) \, F\!\left(\frac{n}{d}\right)

其中 $\mu$ 是莫比乌斯函数。

这个公式相当于：把 f 通过因子求和变成 F，再乘以莫比乌斯函数并求和，就能还原 f。就像我们把东西装进盒子（求和），再打开盒子时用莫比乌斯函数这把“钥匙”取出原来的东西。

生活中的类比：猜零花钱的构成

假设你每周的零花钱总额 $F(n)$ 是由几个不同来源的零花钱 $f(d)$ 加起来的，而且 $F(n)$ 包含了所有能被 $n$ 整除的“来源编号”对应的钱。比如，你不知道你从爸爸、妈妈、爷爷那里各得多少，只知道每周总钱数等于这些来源钱数的和（当来源编号是周数的因子时）。那么莫比乌斯反演就像用“差值”的方法，一步步把每个来源的钱数算出来。

什么是莫比乌斯函数 $\mu(n)$ ？

莫比乌斯函数是一个很简单的“符号”函数：

$\mu(1) = 1$
如果 $n$ 有平方因子（即能被某个质数的平方整除），则 $\mu(n) = 0$
否则， $n$ 是不同质数的乘积，假设有 $k$ 个质数，则 $\mu(n) = (-1)^k$

例如：

$\mu(1)=1$ ， $\mu(2)=(-1)^1=-1$ ， $\mu(3)=-1$ ， $\mu(4)=0$ （因为 $4=2^2$ ）， $\mu(6)=(-1)^2=1$ （ $6=2\times3$ ）， $\mu(12)=0$ （因为 $12=2^2\times3$ 有平方因子）。

2. 用卷积语言理解

设 $1(n)=1$ ，则 $F = f * 1$ 。而我们已经知道 $\mu * 1 = \varepsilon$ ，所以

F * \mu = (f * 1) * \mu = f * (1 * \mu) = f * \varepsilon = f.

写成求和形式正是反演公式。所以莫比乌斯反演本质上是卷积的逆运算。

什么是狄利克雷卷积？

狄利克雷卷积就像把两个数列“叠在一起求和”。对于两个函数 $f$ 和 $g$ ，它们的卷积定义为：

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

你可以想象成：对于每个因子 $d$ ，把 $f(d)$ 和 $g(n/d)$ 乘起来再求和。这里的 $1$ 函数是常数 1，所以 $F = f * 1$ 就是把所有 $f(d)$ 加起来。

而 $\mu * 1 = \varepsilon$ 是一个特殊结果： $\varepsilon(n)$ 只有在 $n=1$ 时为 1，否则为 0。所以卷积后只有 $n=1$ 时非零，其他项都被抵消了，这就是“逆运算”的关键。

3. 证明（更直观地一步步推导）

为了更直观，我们给出直接证明。要证明 $f(n) = \sum_{d|n} \mu(d) F(n/d)$ 。代入 $F(n/d) = \sum_{k|(n/d)} f(k)$ ，得

\sum_{d|n} \mu(d) \sum_{k|(n/d)} f(k) = \sum_{d|n} \sum_{k|(n/d)} \mu(d) f(k).

交换求和次序：固定 $k$ ，要求 $d$ 满足 $d|n$ 且 $k|(n/d)$ ，即 $d|(n/k)$ 。所以

\sum_{k|n} f(k) \sum_{d|(n/k)} \mu(d) = \sum_{k|n} f(k) \cdot [n/k = 1] = f(n).

其中 $\sum_{d|(n/k)} \mu(d)$ 只有当 $n/k = 1$ 即 $k=n$ 时为1，否则为0（这是莫比乌斯函数的性质：所有正因子 $\mu$ 的和，只有 $m=1$ 时为1，否则为0）。因此右边只剩下 $f(n)$ 。证毕。

新手容易犯的错误

忘记 $\mu(1)=1$ ：在反演求和时， $d=1$ 贡献了 $\mu(1) F(n)$ ，这是最重要的项。如果忘了，结果全错。
搞混因子和倍数：原始公式是 $F(n) = \sum_{d|n} f(d)$ ，反演后是 $f(n) = \sum_{d|n} \mu(d) F(n/d)$ 。注意 $F$ 里面的参数是 $n/d$ ，不是 $d$ 。
求和范围搞错：代码中循环时， $d$ 必须遍历 $n$ 的所有因子，不要漏掉或重复。上面的推导保证了只计算整除的情况。
第二种形式混淆：下面会讲到另一种形式，注意哪种用“因子求和”，哪种用“倍数求和”。

4. 另一形式

有时我们遇到的是形如 $G(n) = \sum_{n|d} g(d)$ 的求和（即倍数求和），也可以反演：

g(n) = \sum_{n|d} \mu(d/n) G(d).

这可以通过变量替换从原始形式推导出来。例如，设 $F(n) = G(1/n)$ ？更直接：令 $f(d) = g(n/d)$ 之类的变化。实际上，如果把 $n$ 看成固定值，原始公式中的 $F$ 是对因子求和，而这里是对 $n$ 的倍数求和，相当于把“因子”和“倍数”互换。在代码实现时，只要把枚举方向调转即可。

假设我们想求满足 $\gcd(a,b)=1$ 且 $1 \le a,b \le N$ 的数对个数。令 $F(k) =$ 满足 $\gcd(a,b)$ 是 $k$ 的倍数的数对个数，则 $F(k) = \lfloor N/k \rfloor^2$ 。又设 $f(k) =$ 满足 $\gcd(a,b)=k$ 的数对个数，则 $F(k) = \sum_{k|d} f(d)$ （因为如果 $\gcd$ 是 $d$ 的倍数，则 $d|\gcd$ ，所以 $k|d$ ）。这是第二种形式的因子求和，反演得 $f(k) = \sum_{k|d} \mu(d/k) F(d)$ 。若求 $f(1)$ ，则 $f(1) = \sum_{d=1}^N \mu(d) \lfloor N/d \rfloor^2$ 。这个公式非常常用，比如统计互质数对。

5. 应用例子

例1：求所有与 n 互质的数的个数。我们知道 $\varphi(n) = \sum_{d|n} \mu(d) \cdot \frac{n}{d}$ 。令 $F(n) = n$ ，则有 $f(n) = \varphi(n)$ ，因为 $n = \sum_{d|n} \varphi(d)$ （欧拉函数恒等式）。反演即得上述公式。

例2：求小于等于 N 且与 N 互质的正整数个数。这就是直接计算 φ(N)。

6. 编程实现反演

给定 F 数组（从1到N），我们可以计算 f 数组。直接按公式枚举因子即可，复杂度 O(N log N)。

6.1 C++ 实现

#include <iostream>
#include <vector>
using namespace std;

// 用线性筛先计算出莫比乌斯函数 mu[1..N]
vector<int> get_mobius(int n) {
    vector<int> mu(n + 1, 0);
    vector<int> primes;               // 存储质数
    vector<bool> is_composite(n + 1, false);  // 标记合数
    mu[1] = 1;                        // μ(1)=1
    for (int i = 2; i <= n; i++) {
        if (!is_composite[i]) {
            primes.push_back(i);      // i是质数
            mu[i] = -1;               // 单质数：(-1)^1 = -1
        }
        for (int p : primes) {
            if (i * p > n) break;
            is_composite[i * p] = true;
            if (i % p == 0) {
                mu[i * p] = 0;        // 有平方因子 p^2
                break;
            } else {
                mu[i * p] = mu[i] * mu[p];  // 互质时乘积
            }
        }
    }
    return mu;
}

// 莫比乌斯反演：给定 F[1..n]，计算 f[1..n] 使得 F = f * 1
vector<long long> mobius_inversion(const vector<long long>& F, const vector<int>& mu) {
    int n = F.size() - 1;              // 数组大小，F[0] 不使用
    vector<long long> f(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        long long sum = 0;             // 临时和
        // 枚举 i 的所有因子 d
        for (int d = 1; d <= i; d++) {
            if (i % d == 0) {          // d 是 i 的因子
                sum += mu[d] * F[i / d];
            }
        }
        f[i] = sum;
    }
    return f;
}

int main() {
    const int N = 100;
    // 假设我们知道 F(n) = n，即 id 函数，那么 f 应该是 φ (欧拉函数)
    vector<long long> F(N + 1, 0);
    for (int i = 1; i <= N; i++) F[i] = i;
    vector<int> mu = get_mobius(N);
    vector<long long> f = mobius_inversion(F, mu);
    cout << "反演得到的 f(n) (应该是欧拉函数) 前10项:" << endl;
    for (int i = 1; i <= min(N, 10); i++) {
        cout << "f(" << i << ") = " << f[i] << endl;
    }
    // 验证：欧拉函数 φ(n) 的已知值
    // φ(1)=1, φ(2)=1, φ(3)=2, φ(4)=2, φ(5)=4, φ(6)=2, φ(7)=6, φ(8)=4, φ(9)=6, φ(10)=4
    return 0;
}

6.2 Python 实现

def get_mobius(n):
    """返回莫比乌斯函数数组 mu[0..n]"""
    mu = [0] * (n + 1)
    primes = []                      # 存储质数
    is_composite = [False] * (n + 1) # 标记合数
    mu[1] = 1                        # μ(1)=1
    for i in range(2, n + 1):
        if not is_composite[i]:
            primes.append(i)
            mu[i] = -1               # 单质数：(-1)^1 = -1
        for p in primes:
            if i * p > n:
                break
            is_composite[i * p] = True
            if i % p == 0:
                mu[i * p] = 0        # 有平方因子 p^2
                break
            else:
                mu[i * p] = mu[i] * mu[p]  # 互质时乘积
    return mu

def mobius_inversion(F, mu):
    """给定 F[1..n], 返回 f[1..n] 使得 F = f * 1"""
    n = len(F) - 1
    f = [0] * (n + 1)
    for i in range(1, n + 1):
        total = 0
        # 枚举 i 的所有因子 d
        for d in range(1, i + 1):
            if i % d == 0:          # d 是 i 的因子
                total += mu[d] * F[i // d]
        f[i] = total
    return f

# 测试
N = 100
F = [0] + list(range(1, N + 1))   # id 函数
mu = get_mobius(N)
f = mobius_inversion(F, mu)
print("反演得到的 f(n) (应该是欧拉函数) 前10项:")
for i in range(1, min(N, 10) + 1):
    print(f"f({i}) = {f[i]}")
# 输出期望:
# f(1)=1, f(2)=1, f(3)=2, f(4)=2, f(5)=4, f(6)=2, f(7)=6, f(8)=4, f(9)=6, f(10)=4

常见编程错误提醒

数组越界：莫比乌斯函数和 F 数组通常从下标 1 开始，0 号位置不用。循环时注意 F[i/d] 中的 i/d 可能为 0？不会，因为 d ≤ i，i/d ≥ 1。
整数除法：C++中 i/d 是整数除法，但这里 d 是 i 的因子，结果正好是整数。Python 中 // 也是整数除法。
数据类型：F 的值可能很大，用 long long 或 Python 的 int 避免溢出。
莫比乌斯函数计算：线性筛的写法要正确，特别是 i%p==0 时 break 并设置 mu=0，否则会出错。

7. 验证反演正确性的完整示例

我们可以用已知的欧拉函数恒等式来验证反演公式：已知 $n = \sum_{d|n} \varphi(d)$ ，那么如果取 $F(n)=n$ ，反演得到的 $f(n)$ 应该等于 $\varphi(n)$ 。上面的代码运行后，前10项结果应该和欧拉函数一致。同学们可以手动计算几个验证：

对于 n=6，因子有 1,2,3,6。F(6)=6，F(3)=3，F(2)=2，F(1)=1。反演：f(6) = μ(1)*F(6) + μ(2)*F(3) + μ(3)*F(2) + μ(6)F(1) = 16 + (-1)*3 + (-1)2 + 11 = 6-3-2+1=2，而 φ(6)=2，正确。

8. 小结

莫比乌斯反演是数论中最重要的工具之一，它将因子求和与莫比乌斯函数联系起来，提供了将求和反转的能力。掌握了它，你可以解决许多看似复杂的数论计数问题。记住：用卷积形式 $F = f * 1$ 和 $f = F * \mu$ 是最简洁的记忆方式。

试一试：用反演公式证明 $\varphi(n) = n \sum_{d|n} \frac{\mu(d)}{d}$ 。

莫比乌斯反演公式与证明