这题wa的莫名其妙，郁闷了一下午，队友暴力一发跟我答案也是一样。后来队友说试试把%I64d换成%lld，果然一下ac。。。（暴露了在soj做题少。。

ac之后排在ranklist的最后一名。。。目前也想不到什么优化了。。

还有就是以后对于longlong直接就用cout和cin。。

或者像璟璟说的，热身赛的时候测试一下。。。

题目链接：

http://acm.scu.edu.cn/soj/problem.action?id=4467

题意：

给定n，计算∑gcd(i,n)(i≤n，n<109)。

分析：

想明白一点

如果d是n的一个约数，那么1≤i≤n中gcd(i,n)=d的个数是φ(n/d)

(φ(Nd)代表的是从1到n中与n最大公约数为d的个数)

然后求出因数搞一搞~

代码：

#include<cstdio>

#include<iostream>

#include<cmath>

using namespace std;

typedef long long ll;

const int maxn = 1e6 + 10;

int flag[maxn], prime[maxn];

int tot = 0;

void getprime()

{

    fill(flag, flag + maxn, 1);

    for(int i = 2; i < maxn; i++){

        if(flag[i]){

            prime[tot++] = i;

            for(int j = 2 * i; j < maxn; j += i){

                flag[j] = 0;

            }

        }

    }

}

ll euler(int n)

{

    ll ans = n;

    for(int i = 0; i < tot && prime[i] * prime[i] <= n; i++){

        if(n % prime[i] == 0){

            ans = ans / prime[i] * (prime[i] - 1);

            while(n % prime[i] == 0) n /= prime[i];

        }

    }

    if(n != 1) ans = ans / n * (n - 1);

    return ans;

}

int main (void)

{

    int n;

    getprime();

    while(~scanf("%d", &n)){

        ll ans = 0;

         for(int i = 1; i <= sqrt(n); i++){

            if(n % i == 0){

                ans += euler(n / i) * i;

                if(n / i != i)  ans += euler(i) * (n / i);

            }

         }

         printf("%lld\n", ans);

    }

    return 0;

}