Light OJ 1220 Mysterious Bacteria

题目链接：

http://lightoj.com/volume_showproblem.php?problem=1220

1220 - Mysterious Bacteria

PDF (English)

Statistics

Forum

Time Limit: 0.5 second(s)

Memory Limit: 32 MB

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	Output for Sample Input
3 17 1073741824 25	Case 1: 1 Case 2: 30 Case 3: 2

 

 题目大意：

给你一个x，求满足的p的最大值，b为整数，

思路：

我们质因子分解可以得到，我们实际上求的就是gcd（p1,p2……pn),

因为可以理解为满足条件的gcd保留，其余的数全部相乘起来等于b

 This is the code

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<sstream>
#include<stack>
#include<string>
#include<set>
#include<vector>
using namespace std;
#define PI acos(-1.0)
#define EPS 1e-8
#define MOD 1e9+7
#define LL long long
#define ULL unsigned long long     //1844674407370955161
#define INT_INF 0x7f7f7f7f      //2139062143
#define LL_INF 0x7f7f7f7f7f7f7f7f //9187201950435737471
const int dr[]= {0, 0, -1, 1, -1, -1, 1, 1};
const int dc[]= {-1, 1, 0, 0, -1, 1, -1, 1};
// ios::sync_with_stdio(false);
// 那么cin, 就不能跟C的 scanf，sscanf, getchar, fgets之类的一起使用了。
const int maxn=1e6;
vector<LL > prime;
vector<LL > num;
bool not_prime[maxn+10];//初始为false
LL gcd(LL x,LL y)
{if(!y)return x;return gcd(y,x%y);
}void Prime()
{prime.clear();for(LL i=2; i<=maxn; ++i){if(!not_prime[i])prime.push_back(i);for(LL j=0; j<prime.size()&&prime[j]*i<=maxn; ++j){not_prime[prime[j]*i]=true;if(!(i%prime[j]))//保证没有重复筛选break;}}
}
void work_factor(LL n)
{num.clear();for(int i=0; i<prime.size()&&prime[i]<=n;++i){if(n%prime[i]==0){LL cnt=0;while(n%prime[i]==0){++cnt;n=n/prime[i];}num.push_back(cnt);}}if(n!=1)//这一步不能省num.push_back(1);
}
LL slove(LL n)
{bool flag=true;if(n<0){n=abs(n);flag=false;}work_factor(n);LL t=num[0];if(!flag){while(t%2==0)t/=2;for(int i=0;i<num.size();++i){while(num[i]%2==0)num[i]/=2;t=gcd(t,num[i]);}return t;}for(int i=0;i<num.size();++i)t=gcd(t,num[i]);return t;
}
int main()
{Prime();int T;scanf("%d",&T);for(int t=1;t<=T;++t){LL n;scanf("%lld",&n);printf("Case %d: %d\n",t,slove(n));}return 0;
}