[bzoj3994]约数个数和_C

概述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

 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]]=-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,&m);37         if (n>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 }