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