题目链接：
?id=2480
题目大意：
给一个正整数n，求Σgcd(i，n)，(1 <= i <= n)。
思路：
如果m，n互质，则gcd(i，，m*n) = gcd(i，m) * gcd(i，n)，所以gcd是乘性函数。
因为乘性函数的和函数也是乘性函数，所以Σgcd(i，N)也是乘性函数。
首先考虑gcd(x，n) = 1，这样的数和刚好为欧拉函数之和sum( φ(n))，现在考虑gcd(x，n) = p
的情况，因为gcd(x/p,n/p) = 1，就变成了欧拉函数之和sum(φ(n/p))，所以gcd(x，n) = p，这种
情况下结果为sum( p*phi(n/p) )，p为n的约数。总结就是Σgcd(i，N) = Σp*phi(n/p)，p是n的约数。
H(p1^k1) * H(p2^k2) * … * H(pn^kn)，
对于素数p^k，有：φ(p^k) = p^k – p^(k-1)，
所以H(pi^ki) = p^k – p^(k-1) + p*(p^(k-1) – p^(k-2)) + p^2*(p^(k-2) – p^(k-3)) + ……
= p^k + k*(p^k – p^(k-1) )
那么解题步骤为将N分解素因子，对每个素因子计算H(pi^ki)，最后加起来。
参考博文：
AC代码：
#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>using namespace std;int main(){__int64 n,i,N,a,p,ans;while(~scanf("%I64d",&n)){N = n;ans = n;for(i = 2; i*i <= N; ++i){if(n % i == 0){a = 0;p = i;while(n % p == 0){a++;n /= p;}ans += ans*a*(p-1)/p;}}if(n != 1)ans += ans*(n-1)/n;printf("%I64d\n",ans);}return 0;}
不论你在什么时候结束，重要的是结束之後就不要悔恨
