题意：calculate ∑gcd(i, N) 1<=i <=N. 又一个水题，为了加深印象。
转化为欧拉函数之和即可。注意不要直接枚举，那样会超时，应sqrt枚举。
- #include <stdio.h>
- #include <string.h>
- #include <iostream>
- using namespace std;
- #define N 1000005
- typedef long long LL;
- bool prime[N];
- LL p[N];
- LL k=0;
- void isprime()
- {
- LL i,j;
- memset(prime,true,sizeof(prime));
- for(i=2;i<N;i++)
- {
- if(prime[i])
- {
- p[k++]=i;
- for(j=i+i;j<N;j+=i)
- {
- prime[j]=false;
- }
- }
- }
- }
- LL phi(LL n)
- {
- LL rea=n,i;
- for(i=0;p[i]*p[i]<=n;i++)
- {
- if(n%p[i]==0)
- {
- rea=rea-rea/p[i];
- while(n%p[i]==0) n/=p[i];
- }
- }
- if(n>1)
- rea=rea-rea/n;
- return rea;
- }
- int main()
- {
- LL i,n,ans;
- isprime();
- while(cin>>n)
- {
- ans=0;
- for(i=1;i*i<=n;i++)
- {
- if(i*i==n)
- ans+=i*phi(n/i);
- else if(n%i==0)
- ans+=i*phi(n/i)+(n/i)*phi(i);
- }
- cout<<ans<<endl;
- }
- return 0;
- }