数论题集1-8-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

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

题意：言简意赅！！！

就是给你一个数 N  ， N = x ^ p  求  p  的 最大值

emmm......一眼看起来好像挺好写

唯一分解定理嘛 ， N = x1^p1 * x2^p2 * x3^p3 *............*xn^pn

然后去找max(p1 , p2 , ...,pn)

真好 ，然而 题意当然不是这样的。。。。。。

题目说求N = x ^ p 中 p 的最大值 ， 也就是说只有一个质因子

比如 12 = 2^2 * 3 ^1     答案是2 ？no!!!! 

12 = 12^1   答案是 1

还有就是N的值可能是负数~~只有负数的奇次方才能为负数，

so.......如果求出来的p是偶数的话 ，我们要不断的除2 ， 直到为奇数再输出

注意！！！

N要开 long long  不然过不了

还有！！！

筛法求素数的时候，不要加sqrt()了 ， 血的教训啊~~

下面代码：

#include <bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
const int maxn = 1e5+10;
bool vis[maxn] = {0};
int prime[maxn];
int ret;
void IsPrime()
{
	ret = 0;
	vis[1] = 1;
	for(int i = 2 ; i <= maxn ; i++)
	{
		if(vis[i] == 0)
		{
			prime[ret++] = i;
			for(int j = 2 ; j * i < maxn ; j++)
			{
				vis[i*j] = 1;
			}
		}
	}
}
signed main()
{
	int t , ans;
	ll n;
	IsPrime();
	cin >> t;
	for(int k = 1 ; k <= t ; k++)
	{
		cin >> n;
		int sum = 0 ;
		int flag = 0;
		if(n < 0)
		{
			n = -n;
			flag = 1;
		}
		for(int i = 0 ; i < ret ; i++)
		{
			if(n % prime[i] == 0)
			{
				ans = 0;
				while(n % prime[i] == 0)
				{
					ans++;
					n /= prime[i];
				}
				if(sum == 0)
				{
					sum = ans;
				}
				else
				{
					sum = __gcd(sum , ans);
				}	
			}
		}
		if(n > 1)
		{
			sum = 1;
		}
		if(flag == 1)
		{
			while(sum % 2 == 0)
			{
				sum = sum/2;
			}
		}
		printf("Case %lld: %lld\n" , k , sum);
	}
	return 0;
 }