修改自：
http://hi.baidu.com/arorua_/item/381bb88d817b122d100ef3a1Number one：poj2480
http://poj.org/problem?id=2480题意是：求
∑gcd(i, N) 1<=i <=N. N(1 < N < 2^31)
解法：
∑gcd(i, n) ==
∑(fac[i] * phi(n / fac[i])) (fac存的是n的所有约数)
代码：
poj2480
//sigma(gcd(i, n)) == sigma(fac[i] * phi(n / fac[i]))
#include <cstdio>
#include <cstring>
using namespace std;
long long n, ans;
int fac[32000], cnt;
//get eular
long long get_eular(long long n) {
long long res = 1;
for (long long i = 2; i * i <= n; i++) {
if (n % i == 0) {
n /= i; res = res * (i - 1);
while (n % i == 0) {
n /= i; res = res * i;
}
}
}
if (n > 1) res *= n - 1;
return res;
}
void get_factor(long long n) {
cnt = 0;
memset(fac, 0, sizeof(fac));
for (int i = 1; (long long)i * i <= n; i++) {
if (n % i == 0) {
if (i * i == n) {
fac[cnt++] = i; return ;
}
fac[cnt++] = i;
fac[cnt++] = n / i;
}
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("p2480", "r", stdin);
#endif
while (scanf("%lld", &n) != EOF) {
ans = 0;
get_factor(n);
for (int i = 0; i < cnt; i++)
ans += fac[i] * (get_eular(n / fac[i]));
printf("%lld\n", ans);
}
return 0;
}