欧拉反演：
核心公式：
$n=\sum \limits_{d|n}^{}\phi(d)$
证明：
统计$1-n$中有多少个数时按与$n$的$gcd$分类即可。
$n=\sum \limits_{d|n}^{} \sum \limits_{i=1}^{n}[gcd(i,n)==d]$
$=\sum \limits_{d|n}^{} \sum \limits_{i=1}^{\frac{n}{d}}[gcd(i,\frac{n}{d})==1]$
$=\sum \limits_{d|n}^{}\phi(\frac{n}{d})$
由约数的对称性，有$n=\sum \limits_{d|n}^{}\phi(d)$。
使用方法：
将所求值反演后推一波式子，可能会降低枚举量。
例：求$\sum \limits_{i=1}^{n}gcd(i,n)$的值。
将$gcd(i,n)$反演，得到原式$=\sum \limits_{i=1}^{n}{\sum \limits_{d|gcd(i,n)}^{}\phi(d)}$
$=\sum \limits_{i=1}^{n}{\sum \limits_{d|i,d|n}^{}{\phi(d)}}$
$=\sum \limits_{d|n}^{}{\sum \limits_{i=1,d|i}^{n}{\phi(d)}}$
$=\sum \limits_{d|n}^{}\phi(d){\sum \limits_{i=1,d|i}^{n}{1}}$
$=\sum \limits_{d|n}^{}\phi(d)\frac{n}{d}$
于是我们把$O(n)$变成了$O(\sqrt{n})$。
莫比乌斯反演：
核心公式：
若$f(n)=\sum \limits_{d|n}^{}g(d)$，则$g(n)=\sum \limits_{d|n}f(d)\mu(\frac{n}{d})$。
其中$\mu(n)=\begin{cases}1 & n=1 \\ (-1)^k & n是k个互异素数的积 \\ 0 & 其他情况 \end{cases}$。
关于$mu(n)$：
性质1：显然它是积性函数。
性质2：$\sum \limits_{d|n}^{}\mu(d)=[n=1]$
证明：从$n$个数中选偶数个的方案数=选奇数个的方案数=$2^{n-1}$。
感性理解一下就是前$n-1$个数随便选或不选，最后一个数视情况而定。
核心公式证明：
由约数的对称性得到$g(n)=\sum \limits_{d|n}f(\frac{n}{d})\mu(d)$
$=\sum \limits_{d|n}{\sum \limits_{i|\frac{n}{d}}g(i)\mu(d)}$
$=\sum \limits_{i|n}{\sum \limits_{d|\frac{n}{i}}g(i)\mu(d)}$
$=\sum \limits_{i|n}{g(i) \sum \limits_{d|\frac{n}{i}}\mu(d)}$
当$\frac{n}{i}=1$时后面的$\mu(d)$之和为1，否则为0。
此时$i=n$，于是原式等价于$g(n)=g(n)$，证毕。
使用方法：
同欧拉反演，也可以将类似于$[gcd(i,j)=1]$反演成$\sum \limits_{d|gcd(i,j)}\mu(d)$进行操作。
技巧：
- 推的时候把$\mu(d)$一直提到最前面，一般会出现一个好康的式子。
- 遇到看起来最简的式子时可以换一个量（乘积之类的）枚举，然后考虑预处理一些东西。
代码（YY的GCD）：
#include<bits/stdc++.h> #define maxn 10000005 #define maxm 500005 #define inf 0x7fffffff #define ll long long #define debug(x) cerr<<#x<<": "<<x<<endl #define fgx cerr<<"--------------"<<endl #define dgx cerr<<"=============="<<endl using namespace std; int x=10000000,p[maxn],mu[maxn],ish[maxn]; int f[maxn],sum[maxn],cnt; inline int read(){ int x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } inline void init(){ mu[1]=1; for(int i=2;i<=x;i++){ if(!ish[i]) p[++cnt]=i,mu[i]=-1; for(int j=1;j<=cnt;j++){ if((int)i*(int)p[j]>x) break; ish[i*p[j]]=1; if(i%p[j]==0) break; mu[i*p[j]]=-mu[i]; } } for(int i=1;i<=x;i++) for(int j=1;j<=cnt;j++){ if((int)i*(int)p[j]>x) break; f[i*p[j]]+=mu[i]; } for(int i=1;i<=x;i++) sum[i]=sum[i-1]+f[i]; } int main(){ init(); int T=read(); while(T--){ int n=read(),m=read(); ll ans=0; for(int l=1,r=0;l<=min(n,m);l=r+1){ r=min(n,min(n/(n/l),m/(m/l))); ans+=(ll)(n/l)*(ll)(m/l)*(ll)(sum[r]-sum[l-1]); } printf("%lld\n",ans); } return 0; }