题解 UVA10622 【完全P次方数 Perfect P-th Powers】
Zesty_Fox
2020-11-06 16:37:06
阅读体验不会更佳:[点这里](https://www.cnblogs.com/acceptedzhs/p/13937575.html)
首先,题目说了数据范围不超过 $int$ ,且绝对值 $\ge 2$ 。这意味着底数一定也 $\ge 2$ 。
那么,我们要枚举的 $p$ 的范围就大大缩小了,一定是在 $[1,32)$ 之间。
对于每一个 $x$ ,我们可以对它进行开根,得到一个浮点数。众所周知,浮点数是有误差的,所以枚举这个浮点数附近几个整数就可以了,不用二分。
最后注意对负数的处理(取绝对值,且 $p$ 只枚举奇数),以及中间运算可能爆 $int$ ,开$long \ long$即可。
$Code:$
```cpp
#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;
}
```