莫比乌斯反演

Summary

莫比乌斯函数 μ(n) 是积性函数：μ(1)=1，n 含平方因子时取 0，否则取负一的 k 次方，k 为 n 的不同质因子个数；它满足 n 的所有因子的 μ 之和等于 n 是否为 1 的指示。莫比乌斯反演给出：若 f(n) 等于 g 在 n 的每个因子上求和，则 g(n) 可用 μ 与 f 的因子求和反解出来。它常用来把 gcd 形式的和式拆开，再配合数论分块在 O(根号 n) 内求解相关计数问题。

参考资料

• 莫比乌斯反演 - OI Wiki

简介

莫比乌斯函数 $\mu(n)$ 是一个积性函数：$\mu(1)=1$；$n$ 含平方因子时 $\mu(n)=0$；否则 $\mu(n)=(-1)^k$，$k$ 为 $n$ 的不同质因子个数。它满足 $\sum_{d\mid n}\mu(d)=[n=1]$。

莫比乌斯反演：若 $f(n)=\sum_{d\mid n}g(d)$，则 $g(n)=\sum_{d\mid n}\mu\left(\frac{n}{d}\right)f(d)$。它常用来把 $\gcd$ 形式的和式拆开，配合数论分块在 $O(\sqrt n)$ 内求解。

例题

洛谷 P3455 [POI 2007] ZAP-Queries

$T$ 组询问，每组给定 $a,b,d$，求 $\sum_{i=1}^a\sum_{j=1}^b[\gcd(i,j)=d]$。