YY的GCD [hard] [莫比乌斯反演]
#include<bits/stdc++.h>
#define N 10000005
#define LL long long
using namespace std;
int p[N],isp[N],mu[N],f[N],T,tot; LL s[N];
void Init(){
mu[1]=1;
for(int i=2;i<=N-5;i++){
if(!isp[i]) p[++tot]=i,mu[i]=-1;
for(int j=1;j<=tot;j++){
if(p[j]*i>N-5) break;
isp[p[j]*i]=1; if(i%p[j]==0) break;
mu[p[j]*i] = -mu[i];
}
}
for(int i=1;i<=N-5;i++)
for(int j=1;j<=tot;j++)
if(p[j]*i<=N-5) f[p[j]*i] += mu[i]; else break;
for(int i=1;i<=N-5;i++) s[i]=(LL)s[i-1]+f[i];
}
void Solve(){
int n,m; scanf("%d%d",&n,&m);
if(n>m) swap(n,m); LL ans=0;
for(int l=1,r;l<=n;l=r+1){
int x1=n/l,x2=m/l;
r=min(n/x1,m/x2);
ans += (LL)(s[r]-s[l-1]) * x1 *x2;
}printf("%lld\n",ans);
}
int main(){
scanf("%d",&T); Init();
while(T--) Solve(); return 0;
}