POJ - 1730 Perfect Pth Powers

向右看齐 2022-05-19 03:59 161阅读 0赞

# **                                      Perfect Pth Powers** #

### **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 p*th* 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 p*th* power.

### **Sample Input** ###

1073741824

### **Sample Output** ###

**题意描述：**

求一个数的最大次方数。（已知n，求x；n=a^x）

**解题思路：**

从网上看了有两种思路：

一种是利用pow()函数直接循环枚举找到符合条件的数，不过要注意精度问题：

x=(int)(pow(n\*1.0,1.0/i)+0.1);

y=(int)(pow(x\*1.0,1.0\*i)+0.1);

另一种是分解质因数，将n分解为多个素数的次方乘积。求着多个素数的次方的最大公约数，即为所求的x；注意若n为负数情况，若n为负数，且得到的最大公约数为偶数，将偶数除以二，直到得到奇数即为所求x（因只有负数的奇数次方才为负数）。

粘一个别人写的枚举的[https://blog.csdn.net/lianai911/article/details/39494291][https_blog.csdn.net_lianai911_article_details_39494291]

思路：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

#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;
    }

分解质因数：

#include<stdio.h>
    #include<math.h>
    #include<string.h>
    # define N 1000000
    int isprime[N];
    int prime[N];
    int gcd(int x,int y)
    {
    	int t;
    	if(y>x)
    		return gcd(y,x); 
    	if(y==0)
    		return x;
    	t=x%y;
    	return gcd(y,t);
    }
    int main()
    {
    	long long n;
    	int m,f,i,j,num,ans,cut,flag;
    	memset(isprime,0,sizeof(isprime));
    	isprime[0]=isprime[1]=1;
    	num=1;
    	for(i=2;i<=N;i++)//筛法将是素数的依次存入数组 
    		if(isprime[i]==0)
    		{
    			prime[num++]=i;
    			for(j=2*i;j<=N;j=j+i)//筛掉素数的整数倍，标记为一 
    				isprime[j]=1;
    		}
    	while(scanf("%lld",&n))
    	{
    		if(n==0)
    			break;
    		flag=0;
    		if(n<0)
    		{
    			flag=1;
    			n=-n;
    		}
    		ans=0;
    		i=0;
    		while(i<num-1&&n>1)
    		{
    			
    			i++;
    			cut=0;
    			while(n%prime[i]==0)
    			{
    				n=n/prime[i];
    				cut++;//统计次方数 
    				
    			}
    			ans=gcd(ans,cut);
    		}
    		if(n!=1)
    			ans=1;
    		if(flag==1)
    		{
    			while(ans%2==0)
    				ans=ans/2;
    		}
    		printf("%d\n",ans);
    		
    	}
    	return 0;
    }

[https_blog.csdn.net_lianai911_article_details_39494291]: https://blog.csdn.net/lianai911/article/details/39494291