POJ 2480 Longge's problem

問題

整数Nに対してΣ[i=1,N]gcd(i,N)を求めよ。

制約条件

N<2^31

方針

gcd(k,n)が等しいものをまとめて足す。
d=gcd(k,n)とおけば、
kはdの倍数であるので、d=gcd(d*t,n)=d*gcd(t,n/d)となり、
gcd(t,n/d)=1であるようなtの個数が、gcd(k,n)=dであるものの個数に一致することがわかる。


これはオイラー関数をφとすれば、φ(n/d)の値そのものである。

ソースコード

map<int,int> prime_factor(int n){
  map<int,int> res;
  for(ll i=2;i*i<=n;i++)while(n%i==0){
    res[i]++;
    n/=i;
  }
  if(n>1)res[n]++;
  return res;
}
vi divisor(int n){
  vi res;
  for(ll i=1;i*i<=n;i++)if(n%i==0){
    res.pb(i);
    if(i*i!=n)res.pb(n/i);
  }
  return res;
}
int main(){
  int n;
  while(cin>>n){
    
    map<int,int> primes=prime_factor(n);
    vi divs=divisor(n);
    
    ll res=0;
    
    rep(i,divs.size()){
      ll euler=divs[i];
      fr(it,primes){
        int p=it->first;
        if(divs[i]%p==0)euler=euler/p*(p-1);
      }
      res+=n/divs[i]*euler;
    }
    cout<<res<<endl;
  }
  return 0;
}