题意：求∑gcd(i,n),1<=i<=n
思路：
f(n)=∑gcd(i,n),1<=i<=n
可以知道，其实f(n)=sum(p*φ(n/p))，其中p是n的因子。
为什么呢？原因如下：
1到n中有m个数字和n拥有公共的最大因子p，那么就需要把m*p加入答案中。问题是如何计算m的个数。
因为假设某个数i与n的最大公约数为p，那么gcd(i,n) = p，可以得到gcd(i/p,n/p)=1。也就是说，有多少个i，就有多少个i/p与n/p互质。
那么显然m即为n/p的欧拉函数φ(n/p)。
知道了上述之后，其实我们就可以枚举n的因子p(1<=p<=n)，若p|n，那么答案加上p*φ(n/p)。
不过《数论及应用》p182上面的解法还利用了积性函数。
积性函数是指一个定义域为正整数n 的算术函数f(n)，有如下性质：f(1) = 1，且当a 和b 互质时，f(ab) = f(a) f(b)。
若一个函数f(n) 有如下性质：f(1) = 1，且对两个随意正整数a 和b 而言，不只限这两数互质时，
f(ab) = f(a)f(b) 都成立，则称此函数为完全积性函数。
具体解法可以参见该网址：
http://scturtle.is-programmer.com/posts/19388.html
关于f(N)=∑gcd(i, N)是积性函数的证明参加下面网址：
http://hi.baidu.com/bfcdygoporbjuxr/item/f119741c5fcd9c48e75e06e0
可以推出：f(p^r)=r*(p^r-p^(r-1))+p^r (可以根据φ(p^i)=p^i-p^(i-1)推出)
然后的做法就是将n分解素因子f(n)=f(a1^k1)*f(a2^k2)*...*f(am^km)，利用上述公式求解即可。
我的代码就是参照《数论及应用》p182的解法的。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector> using namespace std;
const int maxn=;
long long N;
bool isprime[maxn];
int prime[maxn];
int cnt=;
void init(){
memset(isprime,true,sizeof(isprime));
for(int i=;i<maxn;i++){
if(isprime[i]){
prime[cnt++]=i;
for(int j=*i;j<maxn;j+=i)
isprime[j]=false;
}
}
}
int main()
{
init();
while(scanf("%lld",&N)!=EOF){
long long ans=;
int r;
for(int i=;i<cnt;i++){
if(N%prime[i]==){
long long ret=;
r=;
while(N%prime[i]==){
N=N/prime[i];
ret*=prime[i];
r++;
}
ans*=r*(ret-ret/prime[i])+ret;
}
}
if(N>){
ans*=N-+N;
}
printf("%I64d\n",ans);
}
return ;
}