题目链接:http://poj.org/problem?id=2480
Time Limit: 1000MS Memory Limit: 65536K

Description

Longge is good at mathematics and he likes to think about hard mathematical problems which will be solved by some graceful algorithms. Now a problem comes: Given an integer N(1 < N < 2^31),you are to calculate ∑gcd(i, N) 1<=i <=N. 

"Oh, I know, I know!" Longge shouts! But do you know? Please solve it. 

Input

Input contain several test case. 
A number N per line. 

Output

For each N, output ,∑gcd(i, N) 1<=i <=N, a line

Sample Input

2
6

Sample Output

3
15

Problem solving report:

Description: 给一个数n,1<=i<=n,求gcd(i,n)之和。
Problem solving: 令d=gcd(i,n)，d必然是n的因子，并且是i和n的最大公因子。求i/d和n/d互质的i在[1,n]里有几个，就等价于 1/d，2/d，...，n/d里面有几个和n/d互质，即φ(n/d)。接着求和约数为d的有φ(n/d)个，所以就是d*φ(n/d)，同时把约数为n/d的加上去，i*i==n特判一下。

Accepted Code:

/* 
 * @Author: lzyws739307453 
 * @Language: C++ 
 */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int pha(int n) {
    int ans = n;
    for (int i = 2; i <= n / i; i++) {
        if (!(n % i)) {
            ans = ans / i * (i - 1);
            while (!(n % i))
                n /= i;
        }
    }
    if (n > 1)
        ans = ans / n * (n - 1);
    return ans;
}
int main() {
    int n;
    while (~scanf("%d", &n)) {
        long long ans = 0;
        for (int i = 1; i <= n / i; i++) {
            if (!(n % i)) {
                ans += i * pha(n / i);
                if (i * i != n)
                    ans += n / i * pha(i);
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}