3994: [SDOI2015]约数个数和

Time Limit: 20 Sec  Memory Limit: 128 MB

Submit: 1164  Solved: 811

[][][]

Description

 设d(x)为x的约数个数，给定N、M，求  

 

 

Input

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

第一行，一个整数T，表示测试数据的组数。

接下来的T行，每行两个整数N、M。

 

Output

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

 

Sample Input

2

7 4

5 6

Sample Output

110

121

HINT

 

 1<=N, M<=50000

1<=T<=50000

 

 

#include
       
        #include
        
         #define maxn 50010using namespace std;int p[maxn],cnt,tot;bool v[maxn];long long n,m,s[maxn],mu[maxn],f[maxn];int main(){    freopen("Cola.txt","r",stdin);    int T;scanf("%d",&T);    s[1]=mu[1]=1;    for(int i=2;i
         
          =maxn)break;            v[p[j]*i]=1;            if(i%p[j]==0){mu[i*p[j]]=0;break;}            else mu[i*p[j]]=-mu[i];        }        s[i]=s[i-1]+mu[i];    }    for(int i=1;i
          
           m)swap(n,m);        long long ans=0;        for(int i=1,j;i<=n;i=j+1){
     //除法分块             j=min(n/(n/i),m/(m/i));            ans+=f[n/i]*f[m/i]*(s[j]-s[i-1]);        }        printf("%lld\n",ans);    }    return 0;}