莫比乌斯反演

What · 是什么

莫比乌斯函数 μ(n) 定义为：μ(1)=1；n 含平方因子则 μ(n)=0；n 为 k 个互异素因子之积则 μ(n)=(−1)^k。它是积性函数，可由线性筛 O(n) 预处理。核心性质 Σ_{d|n} μ(d) = [n=1]。莫比乌斯反演：f(n)=Σ_{d|n} g(d) ⟺ g(n)=Σ_{d|n} μ(n/d)f(d)；倍数形式：f(n)=Σ_{n|d} g(d) ⟺ g(n)=Σ_{n|d} μ(d/n)f(d)。最常见的应用：把 [gcd(i,j)=1]=Σ_{d|gcd(i,j)} μ(d) 代入双重求和，交换求和次序后用数论整除分块 O(√n) 求值。

Why · 为什么

How · 实现

伪代码

# 线性筛预处理 mu[1..N]
mu[1] = 1; primes = []
for i in 2..N:
  if not comp[i]: primes.append(i); mu[i] = -1
  for p in primes:
    if i*p > N: break
    comp[i*p] = True
    if i % p == 0: mu[i*p] = 0; break
    mu[i*p] = -mu[i]

# 求 S = sum_{i=1..n} sum_{j=1..m} [gcd(i,j)=1]
def count_coprime(n, m):
  return sum(mu[d] * (n//d) * (m//d) for d in 1..min(n,m))

# 整除分块优化（多组查询 + 前缀和）:
# sum_{d=l..r} mu[d] 用前缀和 pre[r]-pre[l-1]
# 每次跳到 min(n//(n//d), m//(m//d))

Python 实现

import math
from math import isqrt


def mobius_table(n):
    """线性筛预处理 mu[0..n]，返回 mu 列表。"""
    mu = [0] * (n + 1)
    mu[1] = 1
    primes = []
    comp = [False] * (n + 1)
    for i in range(2, n + 1):
        if not comp[i]:
            primes.append(i)
            mu[i] = -1
        for p in primes:
            if i * p > n:
                break
            comp[i * p] = True
            if i % p == 0:
                mu[i * p] = 0
                break
            mu[i * p] = -mu[i]
    return mu


def mobius_single(x):
    """单点 μ(x)：质因数分解 O(√x)"""
    res = 1
    d = 2
    while d * d <= x:
        if x % d == 0:
            cnt = 0
            while x % d == 0:
                x //= d
                cnt += 1
            if cnt >= 2:
                return 0
            res = -res
        d += 1
    if x > 1:
        res = -res
    return res


def count_coprime_bruteforce(n, m):
    """反演模板：Σ_{i≤n, j≤m} [gcd(i,j)=1] 直接用 mu 求和"""
    mu = mobius_table(max(n, m))
    s = 0
    for d in range(1, min(n, m) + 1):
        s += mu[d] * (n // d) * (m // d)
    return s


def count_coprime_block(n, m):
    """反演 + 整除分块：O(√n)，适合 n,m 达 1e9"""
    mu = mobius_table(isqrt(max(n, m)) + 5)
    pre = [0] * (len(mu))
    for i in range(1, len(mu)):
        pre[i] = pre[i - 1] + mu[i]
    lim = min(n, m)
    s = 0
    d = 1
    while d <= lim:
        qn = n // d
        qm = m // d
        nxt = min(n // qn, m // qm, lim)
        s += (pre[nxt] - pre[d - 1]) * qn * qm
        d = nxt + 1
    return s


if __name__ == "__main__":
    mu = mobius_table(300)
    # 与分解法交叉验证
    for i in range(1, 300):
        assert mu[i] == mobius_single(i), (i, mu[i], mobius_single(i))
    # 核心性质 Σ_{d|n} μ(d) = [n==1]
    for n in range(1, 300):
        s = sum(mu[d] for d in range(1, n + 1) if n % d == 0)
        assert s == (1 if n == 1 else 0), n
    # gcd 互素计数
    for n in range(1, 15):
        for m in range(1, 15):
            brute = sum(1 for i in range(1, n + 1) for j in range(1, m + 1)
                        if math.gcd(i, j) == 1)
            assert count_coprime_bruteforce(n, m) == brute, (n, m)
            assert count_coprime_block(n, m) == brute, (n, m)

    print("All tests passed.")

易错点

• μ 用线性筛求时 i%p==0 分支必须 break 且 mu[i*p]=0，漏 break 会重复标记
• 整除分块的分块上界要 min(n,m)，且 nxt 也要对 lim 取 min 防越界
• 求和项用 (n//d)*(m//d) 先整除再相乘，避免浮点
• 反演方向别弄反：f=Σg ⟺ g=Σμf 的倍数形式（gcd 题常用倍数形式）
• [gcd(i,j)=1] 展开成 Σ_{d|i,d|j} μ(d)，别忘了 d 的上下界是 1..min(n,m)
• 多组查询不预处理 mu 前缀和会导致每组 O(min(n,m)) 超时

例题

信源

• OI Wiki✓ https://oi-wiki.org/math/number-theory/mobius/
• CP-Algorithms✓ https://cp-algorithms.com/algebra/sieve.html
• 书籍✓ CPH ch21 数论（含莫比乌斯反演/整除分块，p.210-216）