51nod 1040：最大公约数之和
题目链接：http://www.51nod.com/onlineJudge/submitDetail.html#!judgeId=222540
题目大意：求$\sum_{i=1}^n gcd(i,n)$.
数论 欧拉函数
求$gcd(i,n)=d$的$i$的个数，即求$gcd(\frac{i}{d},\frac{n}{d})=1$的个数，即求$\varphi(\frac{n}{d})$.
由$\varphi(x)=n \prod (1-\frac{1}{p_i})$，可以在$O(\sqrt{n})$内求得$\varphi(n)$:
1 ll varphi(ll x){ 2 ll ans=1; 3 for(ll i=2;i*i<=x;++i)if(x%i==0){ 4 x/=i;ans*=(i-1); 5 while(x%i==0){ 6 x/=i; 7 ans*=i; 8 } 9 } 10 if(x>1)ans*=(x-1); 11 return ans; 12 }
代码如下：
1 #include <cstdio> 2 using namespace std; 3 typedef long long ll; 4 ll n,ans,d; 5 ll varphi(ll x){ 6 ll ans=1; 7 for(ll i=2;i*i<=x;++i)if(x%i==0){ 8 x/=i;ans*=(i-1); 9 while(x%i==0){ 10 x/=i; 11 ans*=i; 12 } 13 } 14 if(x>1)ans*=(x-1); 15 return ans; 16 } 17 int main(void){ 18 scanf("%lld",&n); 19 for(d=1;d*d<n;++d)if(n%d==0){ 20 ans+=varphi(n/d)*d; 21 ans+=varphi(d)*n/d; 22 }if(d*d==n)ans+=varphi(d)*d; 23 printf("%lld",ans); 24 }
想到用容斥定理的解法，不怎么会计算复杂度，不知是否会T，待更...
原文：http://www.cnblogs.com/barrier/p/6664998.html
