uva10622（唯一分解定理）

 1 #include<cstdio>
 2 #include<cstring>
 3 long long x;  //要用long long 
 4 int cnt;
 5 int pri[50100];  //太小了过不了
 6 int vis[50100];
 7 void is_pri()      //预处理素数表
 8 {
 9     memset(vis,0,sizeof(vis));
10     cnt=0;
11     for(int i=2;i<300;i++) if(!vis[i])
12         for(int j=i*i;j<50100;j+=i)
13             vis[j]=1;
14     for(int i=2;i<50100;i++) if(!vis[i])
15         pri[cnt++]=i;
16 }
17 int gcd(int x,int y)
18 {
19     return y==0?x:gcd(y,x%y);
20 }
21 int maxp(long long x)   //利用唯一分解定理
22 {
23     long long y=x;
24     x=x<0?-x:x;
25     int tmp;
26     int ans=0;
27     for(int i=0;i<cnt&&pri[i]<=x;i++)
28     {
29         tmp=0;
30         while(x%pri[i]==0) {tmp++;x/=pri[i];}
31         ans=gcd(ans,tmp);  //求指数的最大公因数
32     }
33     if(ans==0) return 1;
34     if(y<0) while(ans%2==0) ans/=2;   //对负数特殊处理（偶次方是正数）
35     return ans;
36 
37 }
38 int main()
39 {
40     is_pri();
41     while(scanf("%lld",&x)&&x)
42     {
43         printf("%d
",maxp(x));
44 
45     }
46 }