POJ 1730 Perfect Pth Powers（唯一分解定理）

http://poj.org/problem?id=1730

题意：
给出一个n，a=b^p，求出最大p值。

思路：

首先利用唯一分解定理，把n写成若干个素数相乘的形势。接下来对于每个指数求最大公约数，该公约数就是所能到达的最大p值。

有一点要注意的是如果n为负数的话，如果当前p值为偶数，就一直除2直到p为奇数。

 #include<iostream>

 #include<algorithm>

 #include<string>

 #include<cstring>

 #include<cmath>

 using namespace std;

 const int maxn = ;

 long long n;

 int vis[maxn];

 int prime[];

 int cnt;

 void get_prime()

 {

     cnt = ;

     int m = sqrt(maxn + 0.5);

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

     {

         if (!vis[i])

         {

             prime[cnt++] = i;

             for (int j = i; j < maxn; j += i)

                 vis[j] = ;

         }

     }

 }

 int gcd(int a, int b)

 {

     if (a < b) return gcd(b, a);

     if (b == ) return a;

     return gcd(b, a % b);

 }

 int main()

 {

     //freopen("D:\\txt.txt", "r", stdin);

     get_prime();

     while (~scanf("%lld", &n) && n)

     {

         int flag = ;

         int ans = ;

         if (n < )

         {

             n = -n;

             flag = ;

         }

         int flag2 = ;

         for (int i = ; i < cnt && n>; i++)

         {

             if (n%prime[i] == )

             {

                 int ret = ;

                 while (n%prime[i] == )

                 {

                     n /= prime[i];

                     ret++;

                 }

                 ans = gcd(ans, ret);

             }

         }

         if (n > )  ans = ;

         if (flag)

         {

             while (ans %  == )  ans /= ;

         }

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

     }

 }