POJ 2480

可以容易得知，F=sum(p*phi(n/p))。思路就断在这里了。。。

看过别人的，才知道如下：

由于gcd(i,n*m)=gcd(i,m)*gcd(i,n)，所以gcd为积性函数。而积性函数之和为积性函数。

所以F=sum(gcd(i,n))为积性函数。n=p1^k1*p2^k2....所以f(p1^k1)*f(p2^k2)...=F。

而f(p^r)由最初公式知f(p^r)=r*(p^r-p^(r-1))+p^r。代入以上公式即可求得。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL __int64
using namespace std;

int main(){
	LL n;
	while(scanf("%I64d",&n)!=EOF){
		LL ans=1;
		for(LL i=2;i*i<=n;i++){
			LL r=0,p=1;
			if(n%i==0){
				while(n%i==0){
					p*=i;
					r++;
					n/=i;
				}
				ans*=(r*(p-p/i)+p);
			}
		}
		if(n>1){
			ans*=(1*(n-1)+n);
		}
		printf("%I64d
",ans);
	}
	return 0;
}