2407:Relatives

keyword

約数　包除原理　C++

概要

n(<10^9)が与えられた時にn以下の互いに素な数がいくつあるか求める問題。
オイラーのφ関数使えば解けるけど包除原理使って普通に実装した。

int main(){
    primeTable(100000);
    int n, i, j, ans, d, s, t;

    while(scanf("%d",&n)){
        if(!n) break;
        ans = n-1;
        vector<int> fs;
        t = n;
        for(i=0;i<SZ(ps);i++)if(t%ps[i]==0){
            fs.PB(ps[i]);
            while(t%ps[i]==0) t/=ps[i];
        }
        if(t!=1) fs.PB(t);
        sort(ALL(fs));
        fs.erase(unique(ALL(fs)), fs.end());
        s = SZ(fs);
        vector<int> comb(s);
        REP(i,s){
            REP(j,s){
                if(j<=i) comb[j] = 1;
                else comb[j] = 0;
            }
            do{
                d = 1;
                REP(j,s) d *= (comb[j])?fs[j]:1;
                d = (n-1)/d;
                ans -= (i%2)?-d:d;
            }while(prev_permutation(ALL(comb)));
        }
        printf("%d\n",ans);
    }

    return 0;
}