曾经我好几次想学莫比乌斯反演，但是写完题后还是一脸懵逼，又因为我比较懒，所以已知没有学会，不断摸索摸索，现在已经有了初步的理解。
我决定用初学者的角度写一篇总结，以免我再忘掉。
例题：P3455 [POI2007]ZAP-Queries
实际上就是求
\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=k]
(这里我们让n>=m)
我们首先把k提出来。为什么呢，因为莫比乌斯反演的条件之一是出现[...=1]。即：
\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}[gcd(i,j)=1]
这是因为k|i且k|j时才对答案有贡献。
现在我们先介绍莫比乌斯反演
定义
\mu(x)=\begin{cases} 1 & x=1 \\ 0 & \textrm{存在} p^2|x,p \in Prime \\ (-1)^k & k\textrm{为质因数个数}\end{cases}
非常奇怪的一个定义...
我当初也不太理解为什么要定义成这个鬼样子...
定义
f_1*f_2(x)=\sum_{i|x}f_1(i)f_2(\frac{n}{i})
为数论函数(定义域为正整数的函数)f_1和f_2的迪利克雷卷积
那么实际上我们可以把*看作两个函数之间的作用，返回一个函数
引理1:
若f_1和f_2为积性函数，那么f_1*f_2也为积性函数
证明：
(gcd(x,y)=1)
\begin{aligned} f_1*f_2(xy)=&\sum_{i|xy}f_1(i)f_2(\frac{xy}{i}) -\textrm{定义}\\ =& \sum_{i|x}\sum_{j|y}f_1(ij)f_2(\frac{xy}{ij})-\textrm{把上一步的}i\textrm{变为这一步的ij}\\ =&\sum_{i|x}\sum_{j|y}f_1(i)f_1(j)f_2(\frac{x}{i})f_2(\frac{y}{j}) -f_1\textrm{和}f_2\textrm{是积性函数}\\ =&(\sum_{i|x}f_1(i)f_2(\frac{x}{i}))(\sum_{j|y}f_1(j)f_2(\frac{y}{j}))\ -\textrm{不理解这步的话可以倒推到上一步}\\ =&f_1(x)*f_2(y)\end{aligned}
定义
\epsilon(x)=[x=1]
叫做单位函数
定理1：(反演本质)
1*\mu=\epsilon
即：
\sum_{i|x}\mu(i)=\epsilon(x)
证明：
若x=1，显然成立
否则，我们让t=\Pi_{i=1} p_i^{a_i}
如果a中有一个不为1，则\mu(t)=0
所以对1*\mu真正有贡献的的只有a全为0或1的因数。
假设有p_{1-n}，那么有且仅有i个a的值为1的因数个数为C_{n}^{i}
根据\mu的定义，我们可以得到以下式子
1*\mu=\sum_{i=0}^{n}(-1)^iC_{n}^{i}
而
(x-1)^n=\sum_{i=0}^{n}(-1)^iC_{n}^{i}x^{n-i}
令x=1，等式左边为0，等式右边为上式。所以，这种情况下，
1*\mu=\sum_{i=0}^{n}(-1)^iC_{n}^{i}=0
综上，
1*\mu=\epsilon
引理2：
_证明：_
$(gcd(x,y)=1)
若x和y有一个为1，显然成立
若\mu(x)和\mu(y)有一个为0，显然成立
否则：
\begin{aligned}\mu(x)\mu(y)=&(-1)^{k_x}(-1)^{k_y} -\textrm{定义} \\ =& (-1)^{k_x+k_y} \\ =&\mu(xy) -\textrm{质因数个数函数是加性函数}\end{aligned}
好，说完了一大堆东西，我们继续来看题
\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}[gcd(i,j)=1]
我们使用莫比乌斯反演得到
\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}\sum_{d|gcd(i,j)}\mu(d)
我们又发现可以直接让i变成i/d，j变成j/d，这样就不用考虑d是否是gcd(i,j)的因数，于是我们枚举d，即
\sum_{d=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{kd}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{kd}\rfloor}\mu(d)
此时我们发现，诶！\mu(d)和里面俩\sum没关系了，赶紧提出来
\sum_{d=1}^{n}\mu(d)\sum_{i=1}^{\lfloor\frac{n}{kd}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{kd}\rfloor}1
然后，我们就可以顿时消去两个\sum!
\sum_{d=1}^{n}\mu(d)\lfloor\frac{n}{kd}\rfloor\lfloor\frac{m}{kd}\rfloor
所以我们可以通过线性筛求出\mu(1)-\mu(n)，然后就可以O(n)求了！
但是我们又发现，询问组数T=50000，即使是O(n)也过不去。
此时，我们就需要另外一个数论处理工具：整除分块（数论分块）
对于\sum_{i=1}^{n}f(i)，f(i)单调，f(i)的取值有k种的某些函数，我们可以做到O(k)的复杂度
做法：
- 每次求出f(x)=i的终点
- 统计起点与终点之间的值
- 把i的终点+1为下一个值的起点
为什么说某些函数呢，因为有一些函数你不太好确定终点在哪里。
引理3：
_证明:_
* _若_$d<=\sqrt {\lfloor\frac{n}{k}\rfloor}$_，最多有_$\sqrt {\lfloor\frac{n}{k}\rfloor}$_种取值_
* _若_$d>=\sqrt {\lfloor\frac{n}{k}\rfloor}$，$\lfloor\frac{n}{kd}\rfloor<=\sqrt {\lfloor\frac{n}{k}\rfloor}$_，最多有_$\sqrt {\lfloor\frac{n}{k}\rfloor}$_种取值_
***
于是我们可以$O(n)$预处理，单次询问$O(\sqrt n)$求$\sum_{d=1}^{n}\mu(d)\lfloor\frac{n}{kd}\rfloor\lfloor\frac{m}{kd}\rfloor$啦！注意$\lfloor\frac{n}{kd}\rfloor\lfloor\frac{m}{kd}\rfloor$要分成$\lfloor\frac{n}{kd}\rfloor$和$\lfloor\frac{m}{kd}\rfloor$取值**都一样**的为一段。
代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
const int Maxn=50005;
long long ans;
int T,n,m,k,cnt,mu[Maxn],prim[Maxn],sum[Maxn];
bool vis[Maxn];
void init(void)
{
mu[1]=1;
for(int i=2;i<=50000;i++)
{
if(!vis[i]) prim[++cnt]=i,mu[i]=-1;
for(int j=1;j<=cnt&&i*prim[j]<=50000;j++)
{
vis[i*prim[j]]=true;
if(i%prim[j]==0)
{
mu[i*prim[j]]=0;
break;
}
mu[i*prim[j]]=-mu[i];
}
}
for(int i=1;i<=50000;i++)
sum[i]=sum[i-1]+mu[i];
}
int main()
{
scanf("%d",&T);
init();
while(T--)
{
ans=0;
scanf("%d%d%d",&n,&m,&k);
int End=0,N=n/k,M=m/k;
if(N<M) swap(N,M);
for(int Start=1;Start<=M;Start=End+1)
{
End=min(N/(N/Start),M/(M/Start));
ans+=(sum[End]-sum[Start-1])*(long long)(N/Start)*(M/Start);
}
printf("%lld\n",ans);
}
return 0;
}
```