LightOJ - 1220 Mysterious Bacteria（唯一分解定理）

链接：LightOJ - 1220 Mysterious Bacteria

题意：

给出$x$，求最大的整数$e$满足：存在整数$y$，使得$x=y^e$

$x$是一个32位有符号整数，且保证$|x|\ge 2$

分析：

先假设$x$为正，根据唯一分解定理，得到

$$x=p_1^{a_1}?p_2^{a_2}?p_n^{a_n}$$

存在整数$y$，使得$x=y^e$，即$x^{\frac{1}{e}}=y$，即

$$p_1^{\frac{a_1}{e}}?p_2^{\frac{a_2}{e}}?p_n^{\frac{a_n}{e}}=y$$

上式要等于一个整数，那么一定有$e|a_i$，所以最大的$e$就等于
$$e_{max}=\gcd (a_1,a_2,\dots ,a_n)$$

若$x$为负数，则可以转化为正的先，求得$e_{max}$，但是对于负数$e_{max}$必须为奇数，所以应当让$e_{max}$不断除以$2$，直至变成奇数。

以下代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=1e5+50;
int prime[10000],tot;
bool vis[maxn];
void get_prime()
{
    tot=0;for(int i=2;i<=maxn;i++){
    if(!vis[i])prime[++tot]=i;for(int j=1;j<=tot&&i*prime[j]<=maxn;j++){
    vis[i*prime[j]]=true;if(i%prime[j]==0)break;}}
}
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
LL x;
int ans;
bool neg;
int main()
{
    get_prime();int T,kase=0;scanf("%d",&T);while(T--){
    scanf("%lld",&x);if(x<0){
    x=-x;neg=true;}elseneg=false;ans=0;for(int i=1;i<=tot&&prime[i]*prime[i]<=x;i++){
    if(x%(1LL*prime[i])==0){
    int a=0;while(x%(1LL*prime[i])==0){
    a++;x/=1LL*prime[i];}ans=gcd(ans,a);}}if(x>1)ans=gcd(ans,1);if(neg){
    while(!(ans&1))ans>>=1;}printf("Case %d: %d\n",++kase,ans);}return 0;
}