- #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);
- }
- }
来源: http://www.bubuko.com/infodetail-2961995.html