UVa 10622 (gcd 分解质因数) Perfect P-th Powers

题意：

对于32位有符号整数x，将其写成x = b的形式，求p可能的最大值。

分析：

将x分解质因数，然后求所有指数的gcd即可。

对于负数还要再处理一下，负数求得的p必须是奇数才行。

 #include <cstdio>

 #include <cmath>

 const int maxn = ;

 bool vis[maxn + ];

 int prime[], cnt = ;

 void Init()

 {

     int m = sqrt(maxn + 0.5);

     for(int i = ; i <= m; ++i) if(!vis[i])

         for(int j = i * i; j <= maxn; j += i) vis[j] = true;

     for(int i = ; i <= maxn; ++i) if(!vis[i]) prime[cnt++] = i;

     cnt--;

 }

 int gcd(int a, int b)

 {

     return b ==  ? a : gcd(b, a % b);

 }

 int solve(int n)

 {

     int ans = ;

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

     {

         int k = ;

         while(n % prime[i] == )

         {

             k++;

             n /= prime[i];

         }

         if(k)

         {

             if(k == ) return ;

             ans = gcd(k, ans);

         }

     }

     if(n > ) return ;

     return ans;

 }

 int main()

 {

     Init();

     int n;

     while(scanf("%d", &n) ==  && n)

     {

         int ans = solve(n <  ? -n : n);

         if(n < ) while((ans & ) == ) ans >>= ;

         printf("%d\n", ans);

     }

     return ;

 }

代码君