质数素因子分解+欧筛+负数

Mysterious Bacteria LightOJ - 1220

题目大意：给你一个整数n(可能为负数),让你求满足a^p=n的最大的p
思路：当n是正数时,直接对n进行素因子分解，在对它的素因子的个数进行gcd,比如12=2^2*3,gcd(2,1)就是最大的p;
当n是负数时,则p的值一定是奇数,因为一个数的偶数次方一定为整数，因此需要将它的素因子个数全都化为奇数。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N=200000;
 5 int p[N],c[N];
 6 
 7 void init() {
 8     int num=1;
 9     memset(c,0,sizeof(c));
10     for(int i=2; i<=N; i++) {
11         if(c[i]==0)
12           p[num++]=i;
13         for(int j=1; j<num&&i*p[j]<=N; j++) {
14             c[i*p[j]]=1;
15 
16             if(i%p[j]==0)
17                 break;
18         }
19     }
20 }
21 
22 const int M=35;
23 int a[M],b[M],num;
24 void factor(long long n) {
25     memset(a,0,sizeof(a));
26     memset(b,0,sizeof(b));
27     num=1;
28     int  temp=int(double(sqrt(n))+1);
29     for(int i=1; p[i]<=temp; i++) {
30         if(n%p[i]==0) {
31             a[num++]=p[i];
32             while(n%p[i]==0) {
33                 b[num-1]++;
34                 n/=p[i];
35             }
36         }
37 
38     }
39     if(n!=1)
40     {
41         a[num]=n;
42         b[num]=1;
43     }
44 }
45 int gcd(int a,int b)
46 {
47 return b==0?a:gcd(b,a%b);
48 }
49 int main()
50 {
51     init();
52     int T,po;
53     long long n;
54     scanf("%d",&T);
55     int u=T;
56     while(T--)
57     {
58         int flag=1;
59     scanf("%lld",&n);
60     if(n==1){cout<<"Case "<<u-T<<": "<<1<<endl;continue;}
61 
62     if(n<0)n=-n,flag=0;
63 
64     factor(n);
65     po=b[1];
66     if(flag)
67     for(int i=2;i<num;i++)
68     {
69     po=gcd(po,b[i]);
70     }
71 
72     if(!flag){
73 
74         if(po%2==0){while(po%2==0)po/=2;}
75         for(int i=2;i<num;i++)
76          {
77              if(b[i]%2==0){while(b[i]%2==0)b[i]/=2;}
78            po=gcd(po,b[i]);
79          }
80     }
81     if(b[num])po=gcd(po,b[num]);
82     if(flag)cout<<"Case "<<u-T<<": "<<po<<endl;
83     else if(po%2==1)cout<<"Case "<<u-T<<": "<<po<<endl;
84     else cout<<"Case "<<u-T<<": "<<1<<endl;
85     }
86 }