欧拉函数。
首先设k为n的约数，则res+=(k*s(k))。s(k)为满足gcd(m,n)=k的m的个数。
因为gcd(m,n)=k,所以gcd(m/k,n/k)=1，则s(k) = phi(n/i)。
边界判断要注意。 每次加的为i和n/i。 如果i*i=n，要特判，否则会重复。
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; long long res=0,n; long long phi(long long x) { long long res = x; for(long long i = 2;i*i<=x;i++) if(x%i==0) { res = res/i*(i-1); while(x%i==0) x/=i; } if(x>1) res=res/x*(x-1); return res; } int main() { scanf("%d",&n); long long i; for(i=1;i*i<n;i++) if(n%i==0) { res += (n/i)*phi(i) + i*phi(n/i); } if(i*i==n) res += i*phi(i); printf("%lld\n",res); return 0; }
原文：http://www.cnblogs.com/invoid/p/5432572.html