LightOJ1220

题目链接：http://www.lightoj.com/volume_showproblem.php?problem=1220

题目大意：

　　给你一个 x，请求出一个最大的 p 使得 n^p = x（n为任意整数）。注意，x 有可能是负数。

解题思路：

　　算术基本定理。

　　求出 |x| 的唯一分解式，然后求各项指数的最大公因数。如果 x<0，那么还要事先将分解式的每一项的指数都转化成奇数（负数的偶数次方就变成正数了嘛）。

AC代码：

 #include <iostream>

 #include <cstdio>

 #include <cmath>

 using namespace std;

 typedef long long ll;

 const int maxn = 1e5;

 bool not_prime[maxn];

 int prime[maxn];

 int cnt;

 void init(){

     cnt=;

     not_prime[]=not_prime[]=true;

     for(ll i=;i<maxn;i++){

         if(!not_prime[i]){

             prime[cnt++]=i;

             for(ll j=i*i;j<maxn;j+=i)

                 not_prime[j]=true;

         }

     }

 }

 int gcd(int a,int b){

     if(b==)    return a;

     return gcd(b,a%b);

 }

 int ind[maxn];

 int solve(ll x){

     bool fu=false;

     if(x<){

         fu=true;

         x=-x;

     }

     int tmp=;

     for(int i=;i<cnt;i++){

         if(x%prime[i]==){

             ind[tmp]=; x/=prime[i];

             while(x%prime[i]==){

                 ind[tmp]++;

                 x/=prime[i];

             }

             tmp++;

         }

     }

     if(x>)  ind[tmp++]=;

     if(fu){

         int ret=ind[];

         while(ret%==) ret/=;

         if(ret==)  return ;

         for(int i=;i<tmp;i++){

             while(ind[i]%==)  ind[i]/=;

             ret=gcd(ret,ind[i]);

             if(ret==)  return ;

         }

         return ret;

     }

     else{

         int ret=ind[];

         if(ret==)  return ;

         for(int i=;i<tmp;i++){

             ret=gcd(ret,ind[i]);

             if(ret==)return ;

         }

         return ret;

     }

 }

 int main(){

     init();

     ll x;

     int T;

     scanf("%d",&T);

     for(int t=;t<=T;t++){

         scanf("%lld",&x);

         printf("Case %d: %d\n",t,solve(x));

     }

     return ;

 }

巴特西

LightOJ1220

最新文章

热门文章