困难通用15 分钟5,350 字

莫比乌斯反演公式与证明

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

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

莫比乌斯反演公式​​:如果对于所有正整数 nnn,有

F(n)=∑d∣nf(d)F(n) = \sum_{d|n} f(d)F(n)=d∣n∑​f(d)

那么

f(n)=∑d∣nμ(d) F ⁣(nd)f(n) = \sum_{d|n} \mu(d) , F!\left(\frac{n}{d}\right)f(n)=d∣n∑​μ(d)F(dn​)

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

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

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

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

什么是莫比乌斯函数 μ(n)\mu(n)μ(n)?

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

  • μ(1)=1\mu(1) = 1μ(1)=1
  • 如果 nnn 有平方因子(即能被某个质数的平方整除),则 μ(n)=0\mu(n) = 0μ(n)=0
  • 否则,nnn 是不同质数的乘积,假设有 kkk 个质数,则 μ(n)=(−1)k\mu(n) = (-1)^kμ(n)=(−1)k

例如:

  • μ(1)=1\mu(1)=1μ(1)=1,μ(2)=(−1)1=−1\mu(2)=(-1)^1=-1μ(2)=(−1)1=−1,μ(3)=−1\mu(3)=-1μ(3)=−1,μ(4)=0\mu(4)=0μ(4)=0(因为 4=224=2^24=22),μ(6)=(−1)2=1\mu(6)=(-1)^2=1μ(6)=(−1)2=1(6=2×36=2\times36=2×3),μ(12)=0\mu(12)=0μ(12)=0(因为 12=22×312=2^2\times312=22×3 有平方因子)。

2. 用卷积语言理解

设 1(n)=11(n)=11(n)=1,则 F=f∗1F = f * 1F=f∗1。而我们已经知道 μ∗1=ε\mu * 1 = \varepsilonμ∗1=ε,所以

F∗μ=(f∗1)∗μ=f∗(1∗μ)=f∗ε=f.F * \mu = (f * 1) * \mu = f * (1 * \mu) = f * \varepsilon = f.F∗μ=(f∗1)∗μ=f∗(1∗μ)=f∗ε=f.

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

什么是狄利克雷卷积?

狄利克雷卷积就像把两个数列“叠在一起求和”。对于两个函数 fff 和 ggg,它们的卷积定义为:

(f∗g)(n)=∑d∣nf(d) g ⁣(nd)(f * g)(n) = \sum_{d|n} f(d) , g!\left(\frac{n}{d}\right)(f∗g)(n)=d∣n∑​f(d)g(dn​)

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

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

3. 证明(更直观地一步步推导)

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

∑d∣nμ(d)∑k∣(n/d)f(k)=∑d∣n∑k∣(n/d)μ(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).d∣n∑​μ(d)k∣(n/d)∑​f(k)=d∣n∑​k∣(n/d)∑​μ(d)f(k).

交换求和次序:固定 kkk,要求 ddd 满足 d∣nd|nd∣n 且 k∣(n/d)k|(n/d)k∣(n/d),即 d∣(n/k)d|(n/k)d∣(n/k)。所以

∑k∣nf(k)∑d∣(n/k)μ(d)=∑k∣nf(k)⋅[n/k=1]=f(n).\sum_{k|n} f(k) \sum_{d|(n/k)} \mu(d) = \sum_{k|n} f(k) \cdot [n/k = 1] = f(n).k∣n∑​f(k)d∣(n/k)∑​μ(d)=k∣n∑​f(k)⋅[n/k=1]=f(n).

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

新手容易犯的错误

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

4. 另一形式

有时我们遇到的是形如 G(n)=∑n∣dg(d)G(n) = \sum_{n|d} g(d)G(n)=∑n∣d​g(d) 的求和(即倍数求和),也可以反演:

g(n)=∑n∣dμ(d/n)G(d).g(n) = \sum_{n|d} \mu(d/n) G(d).g(n)=n∣d∑​μ(d/n)G(d).

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

应用例子:数对最大公约数

假设我们想求满足 gcd⁡(a,b)=1\gcd(a,b)=1gcd(a,b)=1 且 1≤a,b≤N1 \le a,b \le N1≤a,b≤N 的数对个数。令 F(k)=F(k) =F(k)= 满足 gcd⁡(a,b)\gcd(a,b)gcd(a,b) 是 kkk 的倍数的数对个数,则 F(k)=⌊N/k⌋2F(k) = \lfloor N/k \rfloor^2F(k)=⌊N/k⌋2。又设 f(k)=f(k) =f(k)= 满足 gcd⁡(a,b)=k\gcd(a,b)=kgcd(a,b)=k 的数对个数,则 F(k)=∑k∣df(d)F(k) = \sum_{k|d} f(d)F(k)=∑k∣d​f(d)(因为如果 gcd⁡\gcdgcd 是 ddd 的倍数,则 d∣gcd⁡d|\gcdd∣gcd,所以 k∣dk|dk∣d)。这是第二种形式的因子求和,反演得 f(k)=∑k∣dμ(d/k)F(d)f(k) = \sum_{k|d} \mu(d/k) F(d)f(k)=∑k∣d​μ(d/k)F(d)。若求 f(1)f(1)f(1),则 f(1)=∑d=1Nμ(d)⌊N/d⌋2f(1) = \sum_{d=1}^N \mu(d) \lfloor N/d \rfloor^2f(1)=∑d=1N​μ(d)⌊N/d⌋2。这个公式非常常用,比如统计互质数对。

5. 应用例子

例1:求所有与 n 互质的数的个数。我们知道 φ(n)=∑d∣nμ(d)⋅nd\varphi(n) = \sum_{d|n} \mu(d) \cdot \frac{n}{d}φ(n)=∑d∣n​μ(d)⋅dn​。令 F(n)=nF(n) = nF(n)=n,则有 f(n)=φ(n)f(n) = \varphi(n)f(n)=φ(n),因为 n=∑d∣nφ(d)n = \sum_{d|n} \varphi(d)n=∑d∣n​φ(d)(欧拉函数恒等式)。反演即得上述公式。

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

6. 编程实现反演

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

6.1 C++ 实现

cpp
#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 实现

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=∑d∣nφ(d)n = \sum_{d|n} \varphi(d)n=∑d∣n​φ(d),那么如果取 F(n)=nF(n)=nF(n)=n,反演得到的 f(n)f(n)f(n) 应该等于 φ(n)\varphi(n)φ(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∗1F = f * 1F=f∗1 和 f=F∗μf = F * \muf=F∗μ 是最简洁的记忆方式。

试一试:用反演公式证明 φ(n)=n∑d∣nμ(d)d\varphi(n) = n \sum_{d|n} \frac{\mu(d)}{d}φ(n)=n∑d∣n​dμ(d)​。

相关指引

  • 狄利克雷卷积​​:进一步学习数论函数间的运算,如 1∗μ=ε1*\mu=\varepsilon1∗μ=ε。
  • 欧拉函数 φ(n)\varphi(n)φ(n)​​:最常见的积性函数,与反演紧密相连。
  • 容斥原理​​:莫比乌斯反演本质上是容斥原理的代数版本,很多计数问题可以用它解决。
  • 其他积性函数​​:如除数函数 σk\sigma_kσk​、莫比乌斯函数本身、Dirichlet 特征等,都可以用类似技巧。

掌握了莫比乌斯反演,你就拥有了一把强大的工具,可以轻松处理“已知总和,求每一项”的难题。快去试试用代码验证更多例子吧!

同类知识点