Dr. Mob has just discovered a Deathly Bacteria. He named it RC-01. RC-01 has a very strange reproduction system. RC-01 lives exactly x days. Now RC-01 produces exactly p new deadly Bacteria where x = bp (where b, p are integers). More generally, x is a perfect pth power. Given the lifetime x 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 integer x. 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 integer p such that x is a perfect pth power.
Sample Input 3 17 1073741824 25 Sample Output Case 1: 1 Case 2: 30 Case 3: 2
给一个数x（可能是负数）求出 使得 x = a ^ b 的 b 的最大值
算术基本定理，x 可以分解成不同的素因子的幂的积，那么找出所有素因子的幂的最小公约数，即为结果。 如果x 为负数，那么先求出 - x 的结果ans，如果 ans 为偶数，说明当前答案不行，应继续将它/2 直到找到一个奇数为止。
#include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<queue> #include<algorithm> #define ll long long #define inf 0x3f3f3f3f #define maxn 100007 //1e5 + 7 using namespace std; bool vis[maxn]; int prime[10010]; int num[1000]; int cnt = 0; void find_prime() { vis[0] = 1; vis[1] = 1; for(int i = 2; i < maxn; i ++) { if(vis[i] == 0) { prime[cnt++] = i; for(int j = i+i; j < maxn; j += i) { vis[j] = 1; } } } } int gcd(int a,int b) { if( a < b) { a = a ^ b; b = b ^ a; a = a ^ b; } return b == 0 ? a : gcd( b ,a % b); } int main() { int t; long long n; find_prime(); scanf("%d",&t); for(int i = 1; i <= t; i ++) { scanf("%lld",&n); int flag = 0; if(n < 0) { n = -n; flag = 1; } if( n == 1 || n == -1) // 1 和 -1 特判下 { printf("Case %d: 1\n",i); continue; } int j = 0; int count = 0; memset(num,0,sizeof(num)); while( j < cnt && prime[j] <= n) { if( n % prime[j] == 0) { while( n % prime[j] == 0) { num[count] ++; n /= prime[j]; // printf(" %d " ,num[count]); } count ++; } j ++; } if( n > 1) //此时说明有个存在一个比较大的素数（该素数不在prime[] 数组中） { // 而且有一个，所以最小公约数为 1，答案为 1 ； printf("Case %d: 1\n",i); continue; } // printf(" __%d__ ",count); if(count == 1) { if(flag == 1 && num[0] % 2 == 0 ) { int tmp = num[0]; // printf("%d ",tmp); while(tmp % 2 == 0) // n 为负数，且所求答案为偶数，不断除2 直到得到奇数答案 { tmp /= 2; } num[0] = tmp; } printf("Case %d: %d\n",i,num[0]); continue; } int tmp = gcd(num[0],num[1]); for(int j = 3; j < count; j ++) tmp = gcd(num[j],tmp); if( flag == 1 && tmp % 2 == 0) // n 为负数，同上 { while( tmp % 2 == 0 ) { tmp /= 2; } } printf("Case %d: %d\n",i,tmp); } return 0; }