Perfect Pth Powers poj1730

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstdio>
 4 #include <math.h>
 5 #define MAXN 100010
 6 #define INF 0x7fffffff
 7 using namespace std;
 8 const int N = 77000 ;
 9 int np[N >> 6], p[N >> 2],ans[N]= {0};
10 void init()
11 {
12     int n = N;
13     p[0] = 1, p[1] = 2;
14     for (int i = 3; i <= n; i++, i++)
15     {
16         if (np[i >> 6] & (1 << ((i >> 1) & 31))) continue;
17         p[++p[0]] = i;
18         for (int j = (i << 1) + i; j <= n; j += (i << 1))
19         {
20             np[j >> 6] |= (1 << ((j >> 1) & 31));
21         }
22     }
23 }
24 int gcd(int x,int y)
25 {
26     if(y==0)return x;
27     return gcd(y,x%y);
28 }
29 int fun(long long x)
30 {
31     int i,ans=0,an=0;
32     bool flag=0;
33     if(x<0)flag=1,x=-x;;
34     for(i=1; x>=p[i]&&i<=p[0]; i++)
35     {
36         if(x%p[i]==0)
37         {
38             ans=0;
39             while(x%p[i]==0)ans++,x/=p[i];
40             if(an==0)an=ans;
41             else
42             {
43                 an=gcd(ans,an);
44             }
45         }
46     }
47     if(x!=1)
48     {
49         an=1;
50     }
51     while(flag&&(an%2==0))an>>=1;
52     if(an==0)return 1;
53     return an;
54 }
55 int main()
56 {
57     init();
58     long long n;
59     while(~scanf("%I64d",&n),n)
60     {
61         printf("%d\n",fun(n));
62     }
63 }