首页 > 代码库 > UVa11424 GCD - Extreme (I)

UVa11424 GCD - Extreme (I)

2024-08-31 20:32:51   209人阅读

直接两重循环O(n^2)算gcd……未免太耗时

枚举因数a和a的倍数n，考虑gcd(i,n)==a的i数量(i<=n)

由于gcd(i,n)==a等价于gcd(i/a,n/a)==1，所以满足gcd(i,n)==a的数有phi[n/a]个

打出欧拉函数表，枚举因数，计算出每个n的f[n]=gcd(1,n)+gcd(2,n)+gcd(3,n)+...+gcd(n-1,n)

然后求f[n]的前缀和，回答询问。

 

 1 /*by SilverN*/ 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 using namespace std; 8 const int mxn=200010; 9 int read(){10     int x=0,f=1;char ch=getchar();11     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}12     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}13     return x*f;14 }15 int pri[mxn],cnt=0;16 long long phi[mxn],f[mxn];17 void PHI(){18     for(int i=2;i<mxn;i++){19         if(!phi[i]){20             phi[i]=i-1;21             pri[++cnt]=i;22         }23         for(int j=1;j<=cnt && (long long)i*pri[j]<mxn;j++){24             if(i%pri[j]==0){25                 phi[i*pri[j]]=phi[i]*pri[j];26                 break;27             }28             else phi[i*pri[j]]=phi[i]*(pri[j]-1);29         }30     }31     return;32 }33 int main(){34     PHI();35     int i,j;36     for(i=1;i<mxn;i++){//枚举因数 37         for(j=i*2;j<mxn;j+=i){38             f[j]+=i*phi[j/i];39         }40     }41     for(i=3;i<mxn;i++)f[i]+=f[i-1];42     while(1){43         i=read();44         if(!i)break;45         printf("%lld\n",f[i]);46     }47     return 0;48 }

 

UVa11424 GCD - Extreme (I)


联系
我们