light oj 1220 Mysterious Bacteria

Mysterious Bacteria  

Time limit 500 ms Memory limit 32768 kB OS Linux

Dr. Mob has just discovered a Deathly Bacteria. He named it RC-01. RC-01 has a very strange reproduction system. RC-01 lives exactlyx days. Now RC-01 produces exactly p new deadly Bacteria wherex = b^p (where b, p are integers). More generally,x is a perfect p^th power. Given the lifetimex of a mother RC-01 you are to determine the maximum number of new RC-01 which can be produced by the mother RC-01.

Input

Input starts with an integer T (≤ 50), denoting the number of test cases.

Each case starts with a line containing an integerx. You can assume that x will have magnitude at least 2 and be within the range of a 32 bit signed integer.

Output

For each case, print the case number and the largest integerp such that x is a perfect p^th power.

Sample Input

3

17

1073741824

25

Sample Output Case 1: 1 Case 2: 30 Case 3: 2 题意：给一个数字n，求能使p^k等于n的最大整数k,n没说是正数还是负数 根据唯一分解定理，每一个数都可以分解成素数乘积组成的因式，求最大的整数k实际就是求因式指数的最大公约数，但是要注意的是n可能小于0，但n小于0是就要将答案中含2的因数全部去掉，因为p^k(k为偶数)>=0的 #include<iostream> #include<algorithm> #include<cmath> #include<cstdio> #include<queue> #include<cstring> #include<string> #include<map> #include<set> using namespace std; typedef long long ll; #define for1(i,a) for(int (i)=1;(i)<=(a);(i)++) #define for0(i,a) for(int (i)=0;(i)<(a);(i)++) #define sf scanf #define pf printf #define mem(i,a) memset(i,a,sizeof i) #define pi acos(-1.0) #define eps 1e-10 const int Max=1e6+7; int p[Max+1],cou,n,T; ll m; bool vis[Max+1]; void prime()//素数打表 { cou=0; mem(vis,0); for(int i=2;i<=Max;i++) { if(!vis[i])p[cou++]=i; for(int j=0;j<cou&&(ll)i*p[j]<=Max;j++) { vis[i*p[j]]=1; if(!(i%p[j]))break; } } } int GCD(int x,int y)//求最大公约数 { return !y?x:GCD(y,x%y); } int main() { prime(); sf("%d",&T); for1(i,T) { sf("%lld",&m); int tag=1; if(m<0)tag=0,m=-m; int ans=0; for(int j=0;j<cou&&p[j]<=sqrt(m);j++)//唯一分解 { int num=0; if(!(m%p[j])) while(!(m%p[j])) num++,m/=p[j]; if(!ans)ans=num;//对ans赋初值 else ans=GCD(ans,num);//对分解的因式的次数求GCD } if(m>1)ans=1; if(!tag)//n小于0的情况要将偶数次幂除去 while(!(ans%2)) ans>>=1; pf("Case %d: %d\n",i,ans); } return 0; }