有时候我们会遇到一类问题：求$f(n)$，当然它是不好直接计算的，但如果$F(n)=\sum\limits_{d|n}f(d)$或$F(n)=\sum\limits_{\substack{n|d\\d\leq m}}f(d)$更易于计算，我们可以用莫比乌斯反演推导出$f(n)$关于$F(n)$的表达式并求值
先定义莫比乌斯函数，若$n=\prod\limits_{i=1}^kp_i^{e_i}$，则莫比乌斯函数$\mu(n)=\begin{cases}1&n=1\\0&\exists e_i\geq2\\\left(-1\right)^k&\forall e_i=1\end{cases}$
从定义可以看出，如果一个整数$n(n\geq2)$含平方因子，那么$\mu(n)=0$，反之，如果它由互异质数相乘而得，那么$质因子个数\mu(n)=(-1)^{\text{质因子个数}}$
莫比乌斯反演定理的一种形式可以描述为“若$F(n)=\sum\limits_{d|n}f(d)$，则$f(n)=\sum\limits_{d|n}\mu(d)F\left(\dfrac nd\right)$”，接下来我们慢慢证明
先证明一个关于莫比乌斯函数的定理：$\sum\limits_{d|n}\mu(d)=[n=1]$，证明如下
有了这个定理，我们就可以证明莫比乌斯反演定理了
$$\begin{align*}\sum\limits_{d|n}\mu(d)F(\dfrac nd)&=\sum\limits_{d|n}\mu(d)\sum\limits_{k|\frac nd}f(k)\\&=\sum\limits_{d|n}\sum\limits_{kd|n}\mu(d)f(k)\\&=\sum\limits_{k=1}^n\sum\limits_{\substack{d|n\\kd|n}}\mu(d)f(k)\\&=\sum\limits_{k=1}^nf(k)\sum\limits_{d|\frac nk}\mu(d)\\&=\sum\limits_{k=1}^nf(k)\left[\dfrac nk=1\right]\\&=f(n)\end{align*}$$
也就是如果$1$和$f$的狄利克雷卷积是$F$，那么$F$和$\mu$的狄利克雷卷积是$f$
这个定理有另一个形式$F(n)=\sum\limits_{n|d}f(d)\Rightarrow f(n)=\sum\limits_{n|d}\mu\left(\dfrac dn\right)F(d)$
因为是倍数和，这里约定$d\leq m$，它的证明是类似的
$$\begin{align*}\sum\limits_{n|d}\mu\left(\dfrac dn\right)F(d)&=\sum\limits_{n|d}\mu\left(\dfrac dn\right)\sum\limits_{d|k}f(k)\\&=\sum\limits_{k=1}^mf(k)\sum\limits_{\substack{n|d\\d|k}}\mu\left(\dfrac dn\right)\\&=\sum\limits_{k=1}^mf(k)\sum\limits_{\frac dn|\frac kn}\mu\left(\dfrac dn\right)\\&=f(n)\end{align*}$$
这个定理可以证明一条联系莫比乌斯函数和欧拉函数的式子，令$f(n)=\varphi(n)$，则$F(n)=n$，用反演定理的形式一可以得到$\varphi(n)=\sum\limits_{d|n}\mu(d)\dfrac nd$，整理得$\dfrac{\varphi(n)}n=\sum\limits_{d|n}\dfrac{\mu(d)}d$，挺优美的
实际做题的时候不一定要用上面的形式，也可以把$[n=1]$换成$\sum\limits_{d|n}\mu(d)$，看能否方便后续计算
下面是真正的应用了：用它来做题
这题要求$\sum\limits_{x=1}^a\sum\limits_{y=1}^b\left[\gcd(x,y)=k\right]$，转化一下就是$\sum\limits_{x=1}^{\left\lfloor\frac ak\right\rfloor}\sum\limits_{y=1}^{\left\lfloor\frac bk\right\rfloor}\left[\gcd(x,y)=1\right]$，于是我们令$f(n)=\sum\limits_{x=1}^{\left\lfloor\frac ak\right\rfloor}\sum\limits_{y=1}^{\left\lfloor\frac bk\right\rfloor}\left[\gcd(x,y)=n\right]$
考虑用反演定理的形式二，得到$F(n)=\sum\limits_{x=1}^{\left\lfloor\frac ak\right\rfloor}\sum\limits_{y=1}^{\left\lfloor\frac bk\right\rfloor}\left[n|\gcd(x,y)\right]=\left\lfloor\dfrac {\left\lfloor\frac ak\right\rfloor}n\right\rfloor\left\lfloor\dfrac{\left\lfloor\frac bk\right\rfloor}n\right\rfloor$，于是$f(n)=\sum\limits_{\substack{n|d\\d\leq\min\left\{\left\lfloor\frac ak\right\rfloor,\left\lfloor\frac bk\right\rfloor\right\}}}\mu\left(\dfrac dn\right)\left\lfloor\dfrac a{kd}\right\rfloor\left\lfloor\dfrac b{kd}\right\rfloor$
答案是$f(1)=\sum\limits_{d=1}^{\min\left\{\left\lfloor\frac ak\right\rfloor,\left\lfloor\frac bk\right\rfloor\right\}}\mu(d)\left\lfloor\dfrac a{kd}\right\rfloor\left\lfloor\dfrac b{kd}\right\rfloor$
学习了一种新的更简洁的写法，这种写法用一种特殊的技巧来快速枚举$d$使得每迭代一次$\left\lfloor\dfrac nd\right\rfloor$就改变一次
for(i=1;i<=n;i=nex+1){
nex=n/(n/i);
//计算[i,nex]的答案
}
循环内的第一行是最重要的，原理大概是这样
这样就解释清楚了为什么要这样写，整个题就做完了
#include<stdio.h>
#define ll long long
#define T 50000
int pr[50010],mu[50010];
bool np[50010];
void sieve(){
int i,j,m;
m=0;
np[1]=1;
mu[1]=1;
for(i=2;i<=T;i++){
if(!np[i]){
m++;
pr[m]=i;
mu[i]=-1;
}
for(j=1;j<=m;j++){
if(pr[j]*(ll)i>T)break;
np[i*pr[j]]=1;
if(i%pr[j]==0){
mu[i*pr[j]]=0;
break;
}else
mu[i*pr[j]]=-mu[i];
}
}
for(i=2;i<=T;i++)mu[i]+=mu[i-1];
}
int a,b;
int min(int a,int b){return a<b?a:b;}
void swap(int&a,int&b){a^=b^=a^=b;}
int F(int n){return(a/n)*(b/n);}
int mob(){
int i,s=0,nex;
if(a>b)swap(a,b);
for(i=1;i<=a;i=nex+1){
nex=min(a/(a/i),b/(b/i));
s+=F(i)*(mu[nex]-mu[i-1]);
}
return s;
}
int main(){
sieve();
int t,d;
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&a,&b,&d);
a/=d;
b/=d;
printf("%d\n",mob());
}
}
感觉写太多字了，有点肝不动...