一、为什么学莫比乌斯反演？
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];
}
}