莫比乌斯反演用来解决一类数论问题。
在开始之前，让我们先了解一些基础知识。
数论函数
在某一整数集合上（一般为全体正整数集）定义的函数称为数论函数。
还记得积性函数的概念吗？对于函数 (f) 和互质的整数 (a,b)，如果 (f(ab)=f(a)f(b))，那么 (f) 就是积性函数。如果 (a,b) 不互质 (f(ab)=f(a)f(b)) 仍然成立，那么 (f) 就是完全积性函数。
举几个常见的数论函数例子，它们也是积性函数：
-
常数函数 (I)（完全积性函数）
(I(n)=1)
有时也写做 (1(n))。
-
单位元函数 (epsilon)（完全积性函数）
(epsilon(n)=[n=1])
有时也写作 (e(n))。
-
恒等函数 (operatorname{id})（完全积性函数）
(operatorname{id}(n)=n)
有时也写作 (Id(n))。
-
约数个数函数 ( au)
( au(n)=sum limits_{d|n} 1)
-
约数和函数 (sigma)
(sigma(n)=sumlimits_{d|n} d)
-
欧拉函数 (varphi)
(varphi(n)=sum limits_{i=1}^{n} [gcd(n,i)=1])
-
莫比乌斯函数 (mu)
(mu(n) = egin{cases} 0 & exists i(p_i>1)\ 1&n=1 or forall i(p_i=1) and 2 mid m \ -1 & ext{otherwise.}end{cases})
其中 (n=prodlimits_{i=1}^{m} p_i^{k_i})，(p_i) 是两两不同的质数。
狄利克雷卷积
定义
对于数论函数 (f,g)，定义二者的狄利克雷卷积为 (f*g)，其中
性质
容易验证，狄利克雷卷积具有以下性质：
-
交换律
[f*g=g*f ] -
结合律
[(f*g)*h=f*(g*h) ]-
证明
注意到
[((f*g)*h)(n) ][=sum limits_{abc=n} f(a)g(b)h(c) ][= sum limits_{a|n} f(a) sum limits_{b| dfrac na} g(b)h(dfrac {n}{ab}) ][= sum limits_{a|n} f(a) (g*h)(dfrac na) ][=(f*(g*h))(n) ]
-
-
分配律
((fpm g)*h=f*h pm g*h)
-
等式性质
[f*h=g*h Leftrightarrow f=g (h(1) eq 0) ]-
证明（参考 OI-Wiki）
右推左显然。
证明左推右，我们先假设 (f eq g)，那么存在最小的 (x) 使得 (f(x) eq g(x))。设 (r=(f-g)*h)，那么有
[r(x)=sum limits_{d|x} (f-g)(d) imes h(dfrac xd) ][=sum limits_{d|x} (f(d)-g(d)) imes h(dfrac xd) ][=(f(x)-g(x)) imes h(1) ][ eq 0 ]因为 (f*h=g*h)，所以 (r=(f-g)*h=0)，矛盾，于是一定有 (f=g)，证毕。
-
-
一个结论
两个积性函数 (f,g) 的狄利克雷卷积仍然是积性函数。
证明：设 (a,b) 互质，则
[(f*g)(a) imes (f*g)(b) ][=sum limits_{d_1|a} f(a)g(dfrac {a}{d_1}) sum limits_{d_2|b} f(b)g(dfrac {b}{d_1}) ]因为 (a) 和 (b) 互质，因此原式可以写作
[sum limits_{d|ab} f(ab)g(dfrac{ab}{d}) ][=(f*g)(ab) ]证毕。
单位元与狄利克雷逆
对于任意数论函数，容易证明，(epsilon*f=f)，所以 (epsilon) 是狄利克雷卷积中的单位元。
如果 (f*g=epsilon)，则称 (f,g) 互为狄利克雷逆。由等式性质可知，一个数论函数的狄利克雷逆唯一。
-
另一个结论
积性函数的狄利克雷逆也是积性函数。
证明可见 OI-Wiki，这里不再证明。
常见数论函数的狄利克雷卷积
-
(mu * I = epsilon)
证明：(n=1) 时显然成立。当 (n>1) 时，设 (n) 的唯一分解式为 (prod limits_{n=1}^{m} p_i^{k_i})，则
[(mu * I)(n)= sum limits_{d|n} mu(d) ][=mu(1)-mu(p_1)-mu(p_2)cdots-mu(p_m)+mu(p_1p_2)+mu(p_1p_3)... ][=1-dbinom m1 + dbinom m2-dbinom m3 + ... ][=(1-1)^m ] -
(I * I = au)
-
(I * operatorname{id} = sigma)
-
(varphi * I = operatorname {id})
即证 (sum limits_{d|n} varphi(d)=n)。
观察到 (1) 到 (n) 中，与 (n) 的最大公约数恰好为 (d) 的数有 (varphi(dfrac nd)) 个。那么上面的式子就是枚举 (d) 求和。
-
(mu * operatorname {id}=varphi)
在上一个式子两侧卷上 (mu)，得 (varphi * I * mu = operatorname{id} * mu)，化简即为上式。
这同时也推导出了 (varphi) 是积性函数。
莫比乌斯反演
对于数论函数 (f,g)，
证明：由左侧可知 (f=g*I)，两边同时卷上 (mu)，得 (g=f * mu)。
接下来看一些例题，如无说明均默认对某一大质数取模。
例题 1 Luogu P2398 GCD SUM
题意
求
(1 leq n leq 10^5)
题解
枚举 (d)，(i,j) 必须是 (d) 的倍数才有贡献，于是有 (left lfloor dfrac nd ight floor) 个 (i) 和 (j) 符合条件，即
线性筛 (varphi) 的前缀和，然后整除分块即可。时间复杂度 (O(n))。
例题 2
题意
求
(10^4) 次询问，每次询问 (1 leq n leq m leq 10^7)
题解
做法和例题 1 类似。
例题 3 Luogu P3455 ZAP-Queries
题意
求
(5 imes 10^4) 组询问，(1 leq n,m leq 5 imes 10^4)
题解
做法和例题 2 类似。
例题 4 HAOI2011 Problem b
题意
求
(5 imes 10^4) 组询问，(1 leq a leq b leq 5 imes 10^4,1 leq c leq d leq 5 imes 10^4,1 leq k leq 5 imes 10^4)
题解
令 (S(n,m)) 表示 (sum limits_{i=1}^{n} sum limits_{j=1}^{m} [gcd(i,j)=k]) 的答案，这就是例题 3。
可以容斥一下，最终的答案就是 (S(b,d)-S(a-1,d)-S(b,c-1)+S(a-1,a-1))。
例题 5 [国家集训队]Crash的数字表格
题意
求
(1 leq n,m leq 10^7)
题解
设 (S(n,m)= sum limits_{i=1}^{n} i sum limits_{j=1}^{m}j cdot [gcd(i,j)=1])。考虑化简 (S)，
可以整除分块求解 (S(n,m))。
此时原式
继续整除分块。
时间复杂度 (O(n))。
例题 6 Luogu P2257 YY 的 GCD
题意
求
(10^4) 组询问，(1 leq n,m leq 10^7)
题解
发现好像化不动了。我们发现瓶颈似乎在于 (sum limits_{p in mathbb P}) 这个求和下标不连续，于是我们把求和顺序交换一下，原式
设 (k=pd)，则原式
于是这个求和下标就连续起来了。设 (f(x)= sum limits_{p in mathbb P and p mid x} mu(dfrac xp))，只要求出 (f) 的前缀和就可以整除分块解决。
来尝试线性筛一下 (f(i))：
-
(i) 是质数
只有 (p=i) 有贡献，(f(i)=mu(1)=1)。
-
枚举到 (x=i imes y)，其中 (y) 是 (x) 的最小质因子
-
(i) 中不包含 (y) 这个质因子
此时 (f(x)) 里面多了一项 (mu(dfrac xy)= mu(i))，并且原来的每一个 (mu(dfrac {i}{p})) 都变成了 (mu(dfrac {iy}{p}))，多了一个质因子，于是 (mu) 值会变为相反数，则有 (f(x)=-f(i)+mu(i))。
-
(i) 中包含 (y) 这个质因子
如果 (i) 中没有多个质因子，那么当 (p=y) 时 (mu(dfrac xp)=mu(i)) 不为 (0)，其余时候都为 (0)，则有 (f(x)=mu(i))。
如果 (i) 中也有多个质因子，那么无论什么时候 (mu(dfrac xp)) 都为 (0)，则有 (f(x)=0)。观察到这个时候有 (mu(i)=0)，于是 (f(x)=mu(i))。可以通过这个手段来简化代码。
-
综上，我们得到了 (f) 的计算式
此时原式
可以整除分块解决。预处理时间复杂度 (O(n))，单词询问 (O(sqrt n))。
例题 7 HDU5382 GCD?LCM!
题意
设
求 (sum limits_{i=1}^n f(i))。
(1 leq n leq 10^6)
题解
我们发现不等式很令人头疼，于是我们找到了另外一个函数
观察到 (f(n)=f(n-1)+2n-1-g(n-1))。其中 (2n-1) 就是 ((1,n),(2,n),cdots,(n,n),(n,1),(n,2),...) 这些有贡献的 (i,j)。观察到 ((n,n)) 算重了，于是要减掉。
我们来化简 (g)：
令 (t(x)= sum limits_{i} sum limits_{j} [ij=d][gcd(i,j)=1])，那么 (t(x)=2^m)，其中 (m) 是 (x) 不同的质因子个数，因为同一种质数不能同时分到 (i,j)。
我们线性筛预处理 (t)，并枚举 (d) 和 (k)，将 (t(dfrac {kd}{d}-1)=t(k-1)) 的贡献加到 (g(kd)) 中，就得到了 (g)。按照递推式便可求出 (f)。时间复杂度 (O(n log n))。