莫比乌斯反演公式与证明
1. 反演:一种“解方程”的思想
想象你有一个秘密数列 f(n)f(n)f(n),但你不知道它。你只知道另一个数列 F(n)=∑d∣nf(d)F(n) = \sum_{d|n} f(d)F(n)=∑d∣nf(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\mu(1)=1μ(1)=1:在反演求和时,d=1d=1d=1 贡献了 μ(1)F(n)\mu(1) F(n)μ(1)F(n),这是最重要的项。如果忘了,结果全错。
- 搞混因子和倍数:原始公式是 F(n)=∑d∣nf(d)F(n) = \sum_{d|n} f(d)F(n)=∑d∣nf(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。
- 求和范围搞错:代码中循环时,ddd 必须遍历 nnn 的所有因子,不要漏掉或重复。上面的推导保证了只计算整除的情况。
- 第二种形式混淆:下面会讲到另一种形式,注意哪种用“因子求和”,哪种用“倍数求和”。
4. 另一形式
有时我们遇到的是形如 G(n)=∑n∣dg(d)G(n) = \sum_{n|d} g(d)G(n)=∑n∣dg(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∣df(d)(因为如果 gcd\gcdgcd 是 ddd 的倍数,则 d∣gcdd|\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++ 实现
#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=∑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∣ndμ(d)。
相关指引
- 狄利克雷卷积:进一步学习数论函数间的运算,如 1∗μ=ε1*\mu=\varepsilon1∗μ=ε。
- 欧拉函数 φ(n)\varphi(n)φ(n):最常见的积性函数,与反演紧密相连。
- 容斥原理:莫比乌斯反演本质上是容斥原理的代数版本,很多计数问题可以用它解决。
- 其他积性函数:如除数函数 σk\sigma_kσk、莫比乌斯函数本身、Dirichlet 特征等,都可以用类似技巧。
掌握了莫比乌斯反演,你就拥有了一把强大的工具,可以轻松处理“已知总和,求每一项”的难题。快去试试用代码验证更多例子吧!