[bzoj3994]约数个数和

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 50005
 4 long long n,m,ans,mu[n],f[n],t[n],vis[n],p[n];
 5 void xxs(int n){
 6     mu[1]=f[1]=1;
 7     for(int i=2;i<=n;i++){
 8         if (!vis[i]){
 9             p[++p[0]]=i;
10             mu[i]=-1;
11             t[i]=1;
12             f[i]=2;
13         }
14         for(int j=1;(j<=p[0])&&(i*p[j]<=n);j++){
15             vis[i*p[j]]=1;
16             if (i%p[j]==0){
17                 t[i*p[j]]=t[i]+1;
18                 f[i*p[j]]=f[i]/(t[i]+1)*(t[i]+2);
19                 break;
20             }
21             t[i*p[j]]=1;
22             f[i*p[j]]=f[i]*2;
23             mu[i*p[j]]=-@H_480_32@mu[i];
24         }
25     }
26     for(int i=2;i<=n;i++){
27         f[i]+=f[i-1];
28         mu[i]+=mu[i-1];
29     }
30 }
31 int main(){
32     xxs(N-5);
33     int t;
34     scanf("%d",&t);
35     while (t--){
36         scanf("%lld%lld",&n,&@H_480_32@m);
37         if (n>@H_480_32@m)swap(n,m);
38         ans=0;
39         for(int i=1,j;i<=n;i=j+1){
40             j=min(n/(n/i),m/(m/i));
41             ans+=(mu[j]-mu[i-1])*f[n/i]*f[m/i];
42         }
43         printf("%lld\n",ans);
44     }
45 }@H_404_306@