PKU 2480 Longge's problem
http://poj.org/problem?id=2480
整数Nが与えられるのでΣgcd(i,N)(1<=i<=N)を計算しろというような問題。
Nの約数iが最大公約数になるようなN以下の数の個数は、φ(n/i)個になるようなので、それを利用して計算しました。
bool npr[1<<20]; ll pr[1<<20]; int sz; ll phi(ll n){ int ret=n; for(int i=0;pr[i]*pr[i]<=n;++i){ if(n%pr[i])continue; ll p=pr[i]; while(n%p==0) n/=p; ret=(ret*(p-1))/(p); } if(n>1)ret=(ret*(n-1))/n; return ret; } main(){ npr[1]=1; for(int i=1;i<(1<<20);++i){ if(npr[i])continue; pr[sz++]=i; for(int j=i*2;j<(1<<20);j+=i)npr[j]=1; } ll n; while(cin>>n){ ll ans=0; for(ll i=1;i*i<=n;++i){ if(n%i)continue; ans+=phi(n/i)*i; ans+=phi(i)*n/i; if(i*i==n)ans-=phi(n/i)*i; } cout<<ans<<endl; } }