PKU (1730 Perfect Pth Powers)

spoiler posted @ 2011年5月01日 22:51 in 数论 , 1029 阅读

题目分析: 就是给你 X 求 最大的p满足 X=a^p  特别提醒一下 X可正可负!

  这里我用的是暴力,就是第一种 枚举+二分,第二种是 比较高效的暴力0MS过的!

这里唯一要考虑的是,首先 如果是正值我们不用做任何处理,如果是负数, 那么他的p肯定不能是偶数,如果是偶数,p次方后 肯定是整数,所以会与答案 有 冲突, 如果还有不懂的 请您留言

代码

#include<stdio.h>
#include<cmath>
#include<iostream>
using namespace std;
int main()
{
  int i;
  double n;
  while(cin>>n,n){
         int maxn=1;
         bool flag=false;
         if(n<0){
               n*=-1;
               flag=true;        
         }
        for(i=32;i>=1;i--){
              double up=ceil(pow(n,1.0/i));
              double down=floor(pow(n,1.0/i));
              if(fabs(n-pow(up,i))<1e-8||fabs(n-pow(down,i))<1e-8) {
                         if(flag){
                                  if(i%2==1){
                                            maxn=i;  break;
                                  }    
                          }    
                          else {
                                maxn=i;
                                break;
                               }                                                 
              }                                
        }
         printf("%d\n",maxn);                       
  }
 return 0;
}
#include<stdio.h>
#include<cmath>
#include<iostream>
using namespace std;
int main()
{
  long long n,i,t,maxn;
  while(cin>>n,n){
         maxn=0;
         bool flag=false;
         if(n<0){
               n*=-1;
               flag=true;        
         }
         long long k=(long long)sqrt(n);
         for(i=2;i<=k;i++){
             long long m=n;
             t=0;
             while(m%i==0){
                    t++;
                    m/=i;            
             } 
             if(m==1){
                      if(flag){
                           if(t%2==1)
                                     maxn=maxn>t? maxn:t;    
                           else 
                                     continue;              
                      }
                     else
                          maxn=maxn>t? maxn:t;         
             }               
         } 
         if(maxn==0)
                    maxn=1;
         printf("%lld\n",maxn);                       
  }
 return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter