LightOj 1220 Mysterious Bacteria

题目大意：

　　给出一个x，求满足x = b^p，p最大是多少？

解题思路：

　　x可以表示为：x = p1^e1 * p2^e2 * p3^e3 ....... * pn^en。

　　p = gcd (e1,e2,.......en);

　　x是负数的时候，p的值不能为偶数，这是坑点之一，还有一个是，题目上说只能用lld，我用的I64d，wa了一下午，想死的冲动都有了，直接上代码，我想静静~~~~~

代码：

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <algorithm>

 #include <iostream>

 #include <cmath>

 using namespace std;

 #define maxn 100010

 int a[maxn], b[maxn];

 int k;

 void prime ()

 {

     long long i, j;

     for(k=, i=; i<maxn; i++)

     {

         if (!a[i])

         {

             b[k ++] = i;

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

                 a[j] = ;

         }

     }

     //printf ("%d\n", k);

 }

 int gcd (int a, int b)

 {

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

 }

 int main ()

 {

     int t, l = ;

     long long n;

     prime();

     scanf ("%d", &t);

     while (t --)

     {

         int ans = , flag = ;

         scanf ("%lld", &n);

         if (n < )

         {

             n =  - n;

             flag = ;

         }

         int i = ;

         while (b[i] < n && i < k)

         {

             if (n % b[i] == )

             {

                 int j = ;

                 while (n % b[i] == )

                 {

                     j ++;

                     n /= b[i];

                 }

                 if (ans == )

                     ans = j;

                 else

                     ans = gcd (ans, j);

             }

             i ++;

         }

         if (n != )//有一个较大的因子没有筛选出来

             ans = ;

         if (flag)//n是负数

             while (ans %  == )

                 ans /= ;

         printf ("Case %d: %d\n", l ++, ans);

     }

     return ;

 }