首页 > itarticle > lightoj Input Output Sample Input Sample Output 题目大意思路代码

lightoj Input Output Sample Input Sample Output 题目大意思路代码

admin 11月 14, 2020 0

传送门:LightOJ-1220

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 = b * p (where b, p are integers). More generally, x is a perfect (p^{th}) 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 (p^{th}) power.

Sample Input

Sample Output

1
2
3

Case 1: 1
Case 2: 30
Case 3: 2

题目大意

题目的意思就是给你一个(x = b^k)，让你找出最大(k)是多少。

思路

这个题思路很明显，我们可以第一时间想到分解质因数，(n = p_1^{e_1}p_2^{e_2}p_3^{e_3}cdots p_n^{e_n})，因为(x = b^k)，所以我们可以让(n = (p_1^{e_1/k}p_2^{e_2/k}p_3^{e_3/k}cdots p_n^{e_n/k})^k)，所以这个题就是找分解质因数后各个因子的指数的最大公约数。但是这个题有个坑点是x可以为负数，那么k就一定是奇数，所以我们在x是负数的时候将x取正，然后求出答案，然后一直除2使其变为奇数。

代码


	> File Name: Mysterious_Bacteria.cpp
	> Author: TSwiftie
	> Mail: [email protected] 
	> Created Time: Wed 21 Aug 2019 08:05:19 AM CST
************************************************************/


#include <string>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <iomanip>
//#include <unordered_map>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e6;
int prime[MAXN+1];
//打素数表
void (){
	memset(prime,0,sizeof prime);
	for(int i = 2;i <= MAXN;i++){
		if(!prime[i])
			prime[++prime[0]] = i;
		for(int j = 1;j <= prime[0]&&prime[j]<=MAXN/i;j++){
			prime[prime[j]*i] = 1;
			if(i%prime[j]==0)
				break;
		}
	}
}
//合数分解
//在分解过程中求gcd
ll getAns(ll x){
	ll tmp = x;
	ll gcd = -1;
	for(int i = 1;prime[i] <= tmp/prime[i];i++){
		if(tmp%prime[i]==0){
			ll cnt = 0;
			while(tmp%prime[i]==0){
				cnt++;
				tmp/=prime[i];
			}
			if(gcd==-1)
				gcd = cnt;
			else
				gcd = __gcd(gcd,cnt);
		}
	}
	if(tmp != 1){
		gcd = 1;
	}
	return gcd;
}
int main(void){
	getPrime();
	int t;
	ll n;
	scanf("%d",&t);
	for(int cas = 1;cas <= t;cas++){
		bool flag = 0;
		scanf("%lld",&n);
		//标记负数
		if(n < 0){
			n = -n;
			flag = 1;
		}
		ll ans = getAns(n);
		//如果是负数就将答案变为奇数
		if(flag)
			while(ans%2==0)
				ans >>= 1;
		printf("Case %d: %lldn",cas,ans);
	}
	return 0;
}