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

Zesty_Fox

2020-11-06 16:37:06

Solution

阅读体验不会更佳:[点这里](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; } ```