一、为什么学莫比乌斯反演？
Mermaid · 渲染中（下方为源码）
graph TD A["F(n)=Σ f(d)"] --> B["f(n)=Σ μ(d)F(n/d)"] B --> C["整除分块 O(√n)"]
在数论与算法竞赛中，常需对"gcd 相关"的求和做优化，如：
- 求
Σ Σ [gcd(i,j)=1]（互质对计数） - 求
Σ Σ gcd(i,j)（最大公约数之和） - 整除分块 + 莫比乌斯函数将 O(n²) 降到 O(n√n)
二、莫比乌斯函数 μ(n)
| n 的素因子分解 | μ(n) |
|---|---|
| 含平方因子 | 0 |
| k 个不同素因子，k 偶 | 1 |
| k 个不同素因子，k 奇 | −1 |
| n = 1 | 1 |
线性筛求 μ：
int[] mu = new int[N];
int[] primes = new int[N];
boolean[] vis = new boolean[N];
int cnt = 0;
mu[1] = 1;
for (int i = 2; i < N; i++) {
if (!vis[i]) { primes[cnt++] = i; mu[i] = -1; }
for (int j = 0; j < cnt && i * primes[j] < N; j++) {
vis[i * primes[j]] = true;
if (i % primes[j] == 0) { mu[i * primes[j]] = 0; break; }
mu[i * primes[j]] = -mu[i];
}
}三、反演公式
若 F(n) = Σ_{d|n} f(d)，则 f(n) = Σ_{d|n} μ(d) · F(n/d)。
常用形式（gcd 互质对）：
Σ_{i=1}^n Σ_{j=1}^m [gcd(i,j)=1] = Σ_{d} μ(d) ⌊n/d⌋⌊m/d⌋
结合整除分块（⌊n/d⌋ 取值只有 O(√n) 种），可 O(√n) 求解。
四、整除分块模板
long solve(int n, int m) {
long ans = 0;
for (int l = 1, r; l <= Math.min(n, m); l = r + 1) {
r = Math.min(n / (n / l), m / (m / l));
ans += (long)(n / l) * (m / l) * (preMu[r] - preMu[l - 1]);
}
return ans;
}五、复杂度
| 项目 | 复杂度 |
|---|---|
| 筛 μ | O(N) |
| 单次互质对查询 | O(√n)（整除分块） |
六、面试要点
- μ 的线性筛与素数筛同源，注意平方因子置 0
- 反演把"gcd 约束"变成"倍数求和"，再整除分块
- 常与欧拉函数 φ 互换使用（gcd 和、互质对）
- 例题：Luogu P2522、POJ 3904 互质四元组