Mysterious Bacteria
题目描述
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 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.
输出
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=b^p 给出x求出最大的p
分析：
唯一分解定理：
每一个大于1的正整数n都可以唯一地写成素数的乘积，在乘积中的素因子按照非降序排列，正整数n的分解式n=（p1^α1）*（p2^α2）*（p3^α3）* ....... *（pk^αk）称为n的标准分解式，其中p1,p2,p3......pk是素数，p1＜p2＜p3.....,且α1，α2，α3.......是正整数。
接下来，最小的p就为gcd(α1,α2,α3......αk），为什么呢？举两个个例子，
24 = 2^3 * 3^1，p应该是gcd(3, 1) = 1,即24 = 24^1，想一想是不是只能把2^3合并到3^1次方里来
324 = 3^4*2^2,p应该是gcd(4, 2) = 2,即324 = 18^2，想一想是不是把3^4合并到2^2次方里来
本题有一个坑点：就是x可能为负数，如果x为负数的话，x = b^q, q必须使奇数，因为偶数的偶数次方大于正数，所以将x转化为正数求得的解如果是偶数的话必须将其一直除2转化为奇数
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<set>
#include<queue>
#include<stack>
#include<map>
#define PI acos(-1.0)
#define in freopen("in.txt", "r", stdin)
#define out freopen("out.txt", "w", stdout)
#define kuaidian ios::sync_with_stdio(0);using namespace std;
typedef long long ll;
const ll N = 5e4+7;
int fac[N],flag;
ll prime[N] = {0},num_prime = 0; //prime存放着小于N的素数
int isNotPrime[N] = {1, 1}; // isNotPrime[i]如果i不是素数，则为1
int Prime()
{ for(ll i = 2 ; i < N ; i ++) { if(! isNotPrime[i]) prime[num_prime ++]=i; //无论是否为素数都会下来 for(ll j = 0 ; j < num_prime && i * prime[j] < N ; j ++){ isNotPrime[i * prime[j]] = 1; if( !(i % prime[j] ) ) //遇到i最小的素数因子//关键处1 break; } } return 0;
} int gcd(int a, int b) {return b == 0 ? a : gcd(b, a%b);
}//与素数筛选一起用的质数分解
///将x分解为式n=（p1^α1）*（p2^α2）*（p3^α3）* ....... *（pk^αk）
///fac求解保存底数p1或者指数α1
void Dec(ll x)
{int cnt = 0;for(int i=0; prime[i]*prime[i]<=x&&i<num_prime; i++){if(x%prime[i]==0){int num=0;while(x%prime[i]==0){num++;x /= prime[i];} fac[cnt++] =num;///如果fac保存的为底数因子（num无用），改为fac[cnt++]=x;}if(x==1) break;}if(x > 1)fac[cnt++] = 1; ///如果fac保存的为底数因子，改为fac[cnt++]=xll ans=0;for(int i = 0; i < cnt; ++i) {ans = gcd(ans, fac[i]);}if(!flag) while(ans % 2 == 0) ans /= 2;cout << ans << endl;
}int main() {int T;Prime();cin >> T;ll n;for(int tt = 1; tt <= T; ++tt) {cin >> n;if(n > 0) flag = 1;else { flag = 0;n *= (-1);}cout << "Case " << tt << ": ";Dec(n);}return 0;
}