首页 > 代码库 > POJ1730_Perfect Pth Powers【水题】

POJ1730_Perfect Pth Powers【水题】

2024-07-23 22:02:29   217人阅读

Perfect Pth Powers
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 16699Accepted: 3786
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


17
1073741824
25
0
Sample Output


1
30
2
Source


Waterloo local 2004.01.31

题目大意：对于一些整数b，n = b^p，（b为正整数）若p最大时，n为完美平方数

给你一个数n，求使n为完美平方数时，最大的p值

思路：p从31到1遍历，求n的p次开方，转为int型的t，再求t的p次方，转为int型的x

若x和n相等，则求得的p为最大值，break出循环

注意：求n的p次开方用pow()求，因为pow()函数得到的为double型，而double型数据

精度问题，比如4可表示为3.99999……或4.0000001，所以转为int型时+0.1

参考博文：http://blog.csdn.net/wangjian8006/article/details/7831478

#include<stdio.h>
#include<math.h>

int main()
{
    int n;
    while(~scanf("%d",&n) && n)
    {
        if(n > 0)
        {
            for(int i = 31; i >= 1; i--)
            {
                int t = (int)(pow(n*1.0,1.0/i) + 0.1);
                int x = (int)(pow(t*1.0,1.0*i) + 0.1);
                if(n == x)
                {
                    printf("%d\n",i);
                    break;
                }
            }

        }
        else
        {
            n = -n;
            for(int i = 31; i >= 1; i-=2)
            {
                int t = (int)(pow(n*1.0,1.0/i) + 0.1);
                int x = (int)(pow(t*1.0,1.0*i) + 0.1);
                if(n == x)
                {
                    printf("%d\n",i);
                    break;
                }
            }
        }
    }
    return 0;
}



POJ1730_Perfect Pth Powers【水题】


联系
我们