初见莫比乌斯反演
有一个套路是关于GCD的反演经常设$f(d)=\sum_{gcd(i,j)==d},g(d)=\sum_{d|gcd(i,j)}$，然后推推推
$\sum\limits_{i=1}^n\sum\limits_{j=1}^m[gcd(i,j)==prime]$
$\sum_{p∈prime}f(p)$
$\sum_{p∈prime} \sum_{d=1}^{min(n,m)} [p|d] μ(\frac{d}{p})g(d)$
套路的，改为枚举$\frac{d}{p}$
$\sum_{p∈prime} \sum_{d=1}^{min(\left\lfloor\frac{n}{p}\right\rfloor,\left\lfloor\frac{m}{p}\right\rfloor)}μ(d)g(dp)$
这时候可以换掉$g$了
$\sum_{p∈prime} \sum_{d=1}^{min(\left\lfloor\frac{n}{p}\right\rfloor,\left\lfloor\frac{m}{p}\right\rfloor)}μ(d)\left\lfloor\frac{n}{dp}\right\rfloor\left\lfloor\frac{m}{dp}\right\rfloor$
然后换回枚举现在的$dp$(即原来的$d$)，交换求和号
$\sum\limits_{i=1}^{min(n,m)}\sum_{d|i\&\&d∈prime}μ(\frac{i}{d})\left\lfloor\frac{n}{i}\right\rfloor\left\lfloor\frac{m}{i}\right\rfloor$
$\sum\limits_{i=1}^{min(n,m)}\left\lfloor\frac{n}{i}\right\rfloor\left\lfloor\frac{m}{i}\right\rfloor\sum_{d|i\&\&d∈prime}μ(\frac{i}{d})$
于是数论分块，前面的直接算，后面的线性筛之后$O(n\log n)$预处理一下再做个前缀和
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
int npr[N],pri[N],mul[N];
long long mulsum[N],ans;
int T,n,m,nm,cnt,maxx;
void prework()
{
register int i,j;
mul[]=,npr[]=true,maxx=;
for(i=;i<=maxx;i++)
{
if(!npr[i]) pri[++cnt]=i,mul[i]=-;
for(j=;j<=cnt&&1ll*i*pri[j]<=maxx;j++)
{
npr[i*pri[j]]=true;
if(i%pri[j]==) break;
else mul[i*pri[j]]=-mul[i];
}
}
for(i=;i<=maxx;i++)
for(j=;j<=cnt&&1ll*i*pri[j]<=maxx;j++)
mulsum[i*pri[j]]+=mul[i];
for(i=;i<=maxx;i++) mulsum[i]+=mulsum[i-];
}
int main()
{
register int i,j;
scanf("%d",&T),prework();
while(T--)
{
scanf("%d%d",&n,&m),ans=,nm=min(n,m);
for(i=;i<=nm;i=j+)
{
j=min(n/(n/i),m/(m/i));
ans+=(mulsum[j]-mulsum[i-])*(n/i)*(m/i);
}
printf("%lld\n",ans);
}
return ;
}