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;
  }
}