SOJ 4467 easyproblem 2【オイラー関数最大公因数和】

この問題waのわけがわからなくて、憂鬱になって午後、チームメートの暴力が私の答えと同じです.后でチームメイトは%I 64 dを%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
", ans);
    }
    return 0;
}