POJ 1730 Perfect Pth Powers 两种方法（质数分解+pow枚举）

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 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​​

算法分析：

题意：

给出一个整数x，把x写成x=a^p，求p最大是多少？

实现

一开是枚举暴力算法，不出所料果然超时，网上看了两种做法

第一种：

a^p*b^p=(a*b)^p,(a^p)^q=a^(p*q)

我们可以看看x的分解质因式：x = a1^b1 * a2^b2 … ak^bk，则最终结果为b1,b2,…bk的最大公约数。

具体的证明，我也不怎么会，

但可以举个例子，我们假设求144，

144=2^4*3^2=(2*3)^2*4=12^2

想一下，要求最大幂，确实都得满足所有质因子的幂次方。

注意负数，那肯定不能为偶数，把2全部取走就行。

第二种：（如果不理解第一种，第二种可以看看，枚举）

p从31到1遍历（2^31= 2147483647,int数据最大范围），求n的p次开方，转为int型的t，再求t的p次方，转为int型的x，解决了pow精度可能不准问题。

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

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

精度问题，比如当用POW（125*1.0，1.0*1/3），直接取整的时候是4，所以需要在后面加一个0.1，也就是（int）（POW(125*1.0,1.0*1/3)+0.1）比如4可表示为3.9999或4.0000001，所以转为int型时+0.1

代码实现：

#include<cstdio>  
#include<cstring>  
#include<cstdlib>  
#include<cctype>  
#include<cmath>  
#include<iostream>  
#include<sstream>  
#include<iterator>  
#include<algorithm>  
#include<string>  
#include<vector>  
#include<set>  
#include<map>  
#include<stack>  
#include<deque>  
#include<queue>  
#include<list> 
using namespace std;
typedef long long ll; 
    
const long N = 70000;   
long prime[N] = {0},num_prime = 0;  //prime存放着小于N的素数   
int isNotPrime[N] = {1, 1};        // isNotPrime[i]如果i不是素数，则为1 
int Prime()    
{     
        for(long i = 2 ; i < N ; i ++)       
        {            
        if(! isNotPrime[i])               
            prime[num_prime ++]=i;  
       //无论是否为素数都会下来     
        for(long j = 0 ; j < num_prime && i * prime[j] <  N ; j ++)
            {               
                isNotPrime[i * prime[j]] = 1;  
            if( !(i % prime[j] ) )  //遇到i最小的素数因子
                //关键处1                  
                break;           
        }        
    }        
    return 0;   
}  
ll gcd(ll a,ll b) { return b == 0 ? a : gcd(b, a % b); }
int main()
{
    ll n;
    Prime();
    while(scanf("%lld",&n)!=EOF)
    {
        int flag=0;
        if(n==0) break;
     if(n<0)
     {
        n=-n;
        flag=1;
     }
     int cnt=0,ans=0;
     for(int i=0;i<num_prime&&n>1;i++)
     {
        cnt=0;
        while(n%prime[i]==0)
        {
        n/=prime[i];
        cnt++;  
        }
        ans=gcd(ans,cnt);
     }
     if(n!=1) ans=1; //说明其为素数 ,一开始忘了竟然超时
     if(flag==1)
     {
        while(ans%2==0)
            ans/=2;
     }
     printf("%d\n",ans);
    }
    return 0;
}

第二种：

#include<cstdio>  
#include<cstring>  
#include<cstdlib>  
#include<cctype>  
#include<cmath>  
#include<iostream>  
#include<sstream>  
#include<iterator>  
#include<algorithm>  
#include<string>  
#include<vector>  
#include<set>  
#include<map>  
#include<stack>  
#include<deque>  
#include<queue>  
#include<list> 
using namespace std;
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;
}

自己chao超时代码

#include<cstdio>  
#include<cstring>  
#include<cstdlib>  
#include<cctype>  
#include<cmath>  
#include<iostream>  
#include<sstream>  
#include<iterator>  
#include<algorithm>  
#include<string>  
#include<vector>  
#include<set>  
#include<map>  
#include<stack>  
#include<deque>  
#include<queue>  
#include<list> 
using namespace std;
typedef long long ll; 
int n;
 
ll quick_qow(ll a,ll b)
{
    long long  res=1;
    while(b>0)
    {
        if(b%2) res=(res*a);
        a=a*a;
        b/=2;
    }
    return res;
}
int isPrime(int n)
{   //返回1表示判断为质数，0为非质数，在此没有进行输入异常检测
    float n_sqrt;
    if(n==2 || n==3) return 1;
    if(n%6!=1 && n%6!=5) return 0;
    n_sqrt=floor(sqrt((float)n));
    for(int i=5;i<=n_sqrt;i+=6)
    {
        if(n%(i)==0 | n%(i+2)==0) return 0;
    }
        return 1;
} 
int main()
{
    ll n;
    

    while(scanf("%lld",&n)!=EOF)
    {
      if(n==0) break;
      if(isPrime(n))  {cout<<1<<endl;continue;}
        int ans;
      for(int i=2;i<=n;i++)
      {
        ll m=n;
        ans=0;
        while(m%i==0)
        {
          m/=i;
          ans++;
        }
        if(m==1)
        {
            cout<<ans<<endl;
            break;
        }
      }
    }
    return 0;
}