菜鸡一个。

题解 UVA10622 【完全P次方数 Perfect P-th Powers】

2020-11-06 16:37:06


阅读体验不会更佳:点这里

首先,题目说了数据范围不超过 $int$ ,且绝对值 $\ge 2$ 。这意味着底数一定也 $\ge 2$ 。

那么,我们要枚举的 $p$ 的范围就大大缩小了,一定是在 $[1,32)$ 之间。

对于每一个 $x$ ,我们可以对它进行开根,得到一个浮点数。众所周知,浮点数是有误差的,所以枚举这个浮点数附近几个整数就可以了,不用二分。

最后注意对负数的处理(取绝对值,且 $p$ 只枚举奇数),以及中间运算可能爆 $int$ ,开$long \ long$即可。

$Code:$

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
ll n;
ll qpow(ll x,int y){
    ll res=1;
    while(y){
        if(y&1) res*=x;
        x*=x;y>>=1;
    }
    return res;
}

int main(){
    while(1){
        scanf("%lld",&n);
        if(n==0) break;
        if(n<0){
            n=-n;
            for(int i=31;i>=1;i-=2){
                ll x=(ll)(pow(n,1.0/i)+0.5);
                for(ll j=x-2;j<=x+1;j++){
                    if(qpow(j,i)==n){
                        printf("%d\n",i);
                        goto nxt;
                    }
                }
            }
        }
        else{
            for(int i=32;i>=1;i--){
                ll x=(ll)(pow(n,1.0/i)+0.5);
                for(ll j=x-2;j<=x+1;j++){
                    if(qpow(j,i)==n){
                        printf("%d\n",i);
                        goto nxt;
                    }
                }
            }
        }
        nxt:;   
    }
    return 0;
}