首页 > 代码库 > POJ 1730 Perfect Pth Powers (枚举||分解质因子)
POJ 1730 Perfect Pth Powers (枚举||分解质因子)
Perfect Pth Powers
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 16638 | Accepted: 3771 |
Description
We say that x is a perfect square if, for some integer b, x = b2. Similarly, x is a perfect cube if, for some integer b, x = b3. More generally, x is a perfect pth power if, for some integer b, x = bp. Given an integer x you are to determine the largest p such that x is a perfect pth power.Input
Each test case is given by a line of input containing x. The value of x will have magnitude at least 2 and be within the range of a (32-bit) int in C, C++, and Java. A line containing 0 follows the last test case.
Output
For each test case, output a line giving the largest integer p such that x is a perfect pth power.
Sample Input
171073741824250
Sample Output
1302
Source
Waterloo local 2004.01.31
从31往前枚举(因为数据最大不会超过32-bit (int))，用pow将要求的数字求出来，再进行验证，这里要注意精度问题。
这道题比较坑的是会有负数，对于负数的话，只能开奇数次方。
1 #include<cmath> 2 #include<cstdio> 3 #include<cstring> 4 #include<stdlib.h> 5 #include<algorithm> 6 #define LL __int64 7 using namespace std; 8 int main() 9 {10 //freopen("in.txt","r",stdin);11 int n,x,y;12 while(scanf("%d",&n)&&n)13 {14 if(n>0)15 {16 for(int i=31;i>=1;i--)17 {18 x=(int)(pow(n*1.0,1.0/i)+0.5);19 y=(int)(pow(x*1.0,1.0*i)+0.5);20 if(n==y)21 {22 printf("%d\n",i);23 break;24 }25 }26 }27 else28 {29 n=-n;30 for(int i=31;i>=1;i-=2)31 {32 x=(int)(pow(n*1.0,1.0/i)+0.5);33 y=(int)(pow(x*1.0,1.0*i)+0.5);34 if(n==y)35 {36 printf("%d\n",i);37 break;38 }39 }40 }41 }42 return 0;43 }
还可以用分解质因子的方法来做
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。