[唯一分解定理+素数筛选]Mysterious Bacteria

题目大意：

给你一个数x = b^p,求p的最大值
分析：x=p1^a1 * p2^a2 . . .pn^an
x只有一个因子的p次幂构成
所以，本题所求实质上就是求 :a1,a2,a3,a4…an的最大公约数

本题有一个坑，就是x可能为负数，如果x为负数的话，x = b^q, q必须使奇数，所以将x转化为正数求得的解如果是偶数的话必须将其一直除2转化为奇数

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
int pri[N];
bool vis[N];
void prime() {
   
	memset(vis,false,sizeof(vis));
	for(int i=2; i<=N; i++) {
   
		if(!vis[i]) {
   
			pri[++pri[0]]=i;
		}
		for(int j=1; j<=pri[0] && i*pri[j]<=N; j++) {
   
			vis[i*pri[j]]=true;
			if(i%pri[j]==0) {
   
				break;
			}
		}
	}
} // 欧拉筛 
int gcd(int a, int b) {
   
	return b ? gcd(b,a%b) : a; 
}

int main()
{
   
	prime();
	int t,cnt=0;
	scanf("%d", &t);
	while(t--) {
   
		bool flag=true;
		ll x,ans=0;        //int范围是-2^31——2^31-1，对于32bit signed interger会爆in
		scanf("%lld", &x);
		//x的值可能小于0 
		if(x<0) {
   
			x=-x;
			flag = false;
		}
		for(int i=1; i<=pri[0]&&pri[i]<=sqrt(x); i++) {
   
			if(x%pri[i]==0) {
   
				int k=0;
				while(x%pri[i]==0) {
   
					x/=pri[i];
					k++;
				}
				if(ans==0) {
   
					ans=k;//第一个 
				}
				else {
   
					ans=gcd(ans,k);
				}
			}
		}
		//如果没有被sqrt内的质数唯一分解，则说明还有有大于sqrt且在分解定理中一次的质数。 
		if(x>1) {
   
			ans=gcd(ans,1);
		}
		//若是负数，则不可能为偶数次方构成 
		if(!flag) {
   
			while(ans%2==0) {
   
				ans/=2;
			}
		}
		printf("Case %d: %d\n",++cnt,ans);	
	}
	return 0;
 }