[bzoj3994]约数个数和
发布时间:2020-12-16 10:48:37 所属栏目:百科 来源:网络整理
导读:1 #includebits/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
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("%lldn",ans); 44 } 45 } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |