1730:Perfect Pth Powers

keyword

素因数分解　C++

概要

xが与えられるとき、x=b^pとなる最大のpを求める問題。
約数の個数の最大公約数を求めるだけだろう、ということはすぐに分かった。素因数分解でなぜかxのルートまで調べればよいだろうと勘違いしてWA。修正したけど通らない。??。入力が負の場合を考えてなかったことに気づく。修正して送信->AC。

int gcds(vector<int> xs){
    int n = SZ(xs), i;
    int ret = xs[0];
    REPONE(i,n-1) ret = __gcd(ret, xs[i]);
    return ret;
}

int main(){
    primeTable(1<<17);
    int i, cnt, sz = SZ(ps), ans;
    ll n;
    bool f;
    while(scanf("%lld",&n)){
        if(!n) break;
        if(n>0) f=false;
        else{f=true;n *= -1;}
        vector<int> facts;
        REP(i,sz){
            cnt = 0;
            while(!(n%ps[i])){cnt++; n/=ps[i];}
            if(cnt) facts.PB(cnt);
        }
        if(n!=1)facts.PB(1);

        ans = gcds(facts);
        if(f)while(!(ans%2))ans/=2;

        printf("%d\n", ans);
    }
    return 0;
}