输入文件包含多组测试数据。

 T行，每行一个整数，表示你所求的答案。

 1<=N, M<=50000

Round 1 感谢yts1999上传

 1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 #define LL long long 9 using namespace std;10 const int mxn=50010;11 int read(){12     int x=0,f=1;char ch=getchar();13     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}14     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}15     return x*f;16 }17 int pri[mxn],cnt=0;18 int mu[mxn],d[mxn],f[mxn];19 //mu:莫比乌斯函数 d[x]:x的最小质因子的次数 f[x]:x的约数个数 20 int smm[mxn];21 bool vis[mxn];22 void init(){23     mu[1]=1;f[1]=1;24     for(int i=2;i<mxn;i++){25         if(!vis[i]){26             mu[i]=-1;27             pri[++cnt]=i;28             d[i]=1;    f[i]=2;29         }30         for(int j=1;j<=cnt && (LL)pri[j]*i<mxn;j++){31             int x=pri[j]*i;32             vis[x]=1;33             if(i%pri[j]==0){//i是x的因数，对f[x]的贡献为(d[i]+2)34                 mu[x]=0;35                 f[x]=f[i]/(d[i]+1)*(d[i]+2);36                 d[x]=d[i]+1;37                 break;38             }39             mu[x]=-mu[i];40             f[x]=f[i]*2;41             d[x]=1;42         }43     }44     for(int i=1;i<mxn;i++){45         smm[i]=smm[i-1]+mu[i];46         f[i]+=f[i-1];47     }48     return;49 }50 LL calc(int n,int m){51     if(n>m)swap(n,m);52     LL res=0;int pos;53     for(int i=1;i<=n;i=pos+1){54         int x=n/i,y=m/i;55         pos=min(n/x,m/y);56         res+=(LL)(smm[pos]-smm[i-1])*(LL)f[x]*f[y];57     }58     return res;59 }60 int n,m;61 int main(){62     int i,j;63     init();64     int T=read();65     while(T--){66         n=read();m=read();67         printf("%lld\n",calc(n,m));68     }69     return 0;70 }