POJ 2480 Longge's problem （积性函数，欧拉函数）

题意：求∑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=67000;
long long N;
bool isprime[maxn];
int prime[maxn];
int cnt=0;
void init(){
    memset(isprime,true,sizeof(isprime));
    for(int i=2;i<maxn;i++){
        if(isprime[i]){
            prime[cnt++]=i;
            for(int j=2*i;j<maxn;j+=i)
                isprime[j]=false;
        }
    }
}
int main()
{
    init();
    while(scanf("%lld",&N)!=EOF){
        long long ans=1;
        int r;
        for(int i=0;i<cnt;i++){
            if(N%prime[i]==0){
                long long ret=1;
                r=0;
                while(N%prime[i]==0){
                    N=N/prime[i];
                    ret*=prime[i];
                    r++;
                }
                ans*=r*(ret-ret/prime[i])+ret;
            }
        }
        if(N>1){
            ans*=N-1+N;
        }
        printf("%I64d
",ans);
    }
    return 0;
}