2478:Farey Sequence

PKU

keyword

動的計画法　φ関数　C++

概要

0

int eulerPhi(int n){
    int ret = n, i, pos = 0;
    if(!table[n]) return n-1;
    while(n>1){
        if(!table[n]){
            fs[pos++] = n;
            break;
        }
        fs[pos++] = table[n];
        while(n%fs[pos-1]==0) n /= fs[pos-1];
    }
    REP(i,pos) ret = ret/fs[i]*(fs[i]-1);
    return ret;
}

int main(){
    int i, n;
    ll dp[1000001];
    REP(i,1000001) table[i] = 0;
    primeTable(1000000);
    dp[2] = 1;
    for(i=3;i<=1000000;i++)dp[i] = dp[i-1] + eulerPhi(i);

    while(scanf("%d",&n)){
        if(!n) break;
        printf("%lld\n", dp[n]);
    }

    return 0;
}