#include<bits/stdc++.h>
using namespace std;
#define maxn 1000005
#define ll long long
int v[maxn],prime[maxn],m;
void init(
int n){
memset(v,0,
sizeof v);
memset(prime,0,
sizeof prime);
m=
0;
for(
int i=
2;i<=n;i++
){
if(v[i]==
0){
v[i]=
i;
prime[++m]=
i;
}
for(
int j=
1;j<=m;j++
){
if(prime[j]>v[i] || prime[j]*i>n)
break;
v[i*prime[j]]=
prime[j];
}
}
}
ll p[1000000],c[
1000000],mm;
void divide(ll n){
memset(p,0,
sizeof p);
memset(c,0,
sizeof c);
mm=
0;
for(
int i=
1;i<=m;i++
){
if(prime[i]>n)
break;
if(n%prime[i]==
0){
p[++mm]=i,c[mm]=
0;
while(n%prime[i]==
0)n/=prime[i],c[mm]++
;
}
}
if(n>
1)p[++mm]=n,c[mm]++
;
}
int main(){
init(1000000);
int T;
ll n;
cin>>
T;
for(
int tt=
1;tt<=T;tt++
){
cin>>
n;
int flag=
0;
if(n<
0)n=-n,flag=
1;
divide(n);
ll Max=
0;
for(
int i=
1;i<=mm;i++
)
Max=
max(Max,c[i]);
ll ans=
0;
for(
int i=
1;i<=mm;i++
)
ans=
__gcd(ans,c[i]);
if(flag){
while(ans%
2==
0)ans/=
2;
}
printf("Case %d: %d\n",tt,ans);
}
}
转载于:https://www.cnblogs.com/zsben991126/p/10408545.html
