传送门
首先得到一个非常显然的柿子
\[\sum_{p} \sum_{d} \lfloor\frac{n}{pd}\rfloor \lfloor\frac{m}{pd}\rfloor
\]
我们可以考虑T=pd，然后转化柿子
\[\sum _{T} \lfloor\frac{n}{T} \rfloor \lfloor\frac{m}{T} \rfloor \sum_{p|T}\mu(\frac{T}{p})
\]
后面这一块可以预处理。然后就是经典的分块，为什么要设T=pd，是因为我们如果你枚举的是p，那么你的d还是要分块，受到n,m的制约，而将其看为一个整体之后我们就可以预处理跟n，m无关的信息，从而快速回答询问。
#include<cstdio>
#include<algorithm>
#include<cstring>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define A puts("YES")
#define B puts("NO")
using namespace std;
typedef long long ll;
const int N=1e7+5;
int p[N],tot,f[N],mu[N];
int t[N],n,m,j,k;
ll ans;
bool vis[N];
int main(){
// freopen("data.in","r",stdin);
mu[1]=1;
fo(i,2,N-1){
if (!vis[i]) {
f[i]=i-1;
mu[i]=-1;
p[++tot]=i;
}
fo(j,1,tot) {
if ((ll)i*(ll)p[j] >= N) break;
vis[i*p[j]]=1;
if (i%p[j]==0) {
f[i*p[j]]=f[i]*p[j];
break;
}
else {
f[i*p[j]]=f[i]*(p[j]-1);
mu[i*p[j]]=-mu[i];
}
}
}
fo(i,1,tot) {
fo(j,1,(N-1)/p[i]) {
t[p[i]*j]+=mu[j];
}
}
fo(i,1,N-1) t[i]+=t[i-1];
int Q;
scanf("%d",&Q);
while (Q--){
scanf("%d %d",&n,&m);
ans=0;
j=1;
while (j<=min(n,m)) {
k=min(n/(n/j), m/(m/j));
ans+=(ll)(n/j)*(ll)(m/j)*(ll)(t[k]-t[j-1]);
j=k+1;
}
printf("%lld\n",ans);
}
return 0;
}