Mysterious Bacteria

题目

图片说明
意思就是给一个数x，现在要将它表示称次方形式，问最高能表示成多少次方？
比如： 25 最高能表示成，它的次方形式表示最高是2次方

分析

这题最开始我写成了二分，按理说是可以过的，但是被WA飞了。
好了，现在讲质因数分解做法。
我们对N进行质因数分解的：
那么如果我们想要讲底数变成一个数，那么我们可以将次方的gcd提取出来，将剩余的数相乘，就比如:
如果N是正数，那么答案就是质因数分解后各个质因数幂的gcd
如果是负数，我们需要将上面得出的gcd减小到最大的一个奇数，so只要不断除以2就行，直到不能够再整除

AC 代码

#include <algorithm>
#include <stdio.h>
#include <cmath>
using namespace std;
typedef long long ll;
const ll maxn = (1LL<<16)+10;


ll T,N;
ll P[maxn],tail;
bool vis[maxn];

ll gcd(ll a,ll b){
    return !b?a:gcd(b,a%b);
}

void init(){
    for(ll i = 2;i<maxn;i++){//素数筛选
        if(!vis[i]){
            P[tail++] = i;
            for(ll j = i*i;j<maxn;j+=i){
                vis[j] = true;
            }
        }
    }
}
ll solve(){
    int tag = 1;
    if(N<0){
        N = - N;
        tag = -1;
    }
    ll g = 0;
    for(ll i = 0;i<tail && P[i]*P[i]<=N;i++){
        if(N%P[i] == 0){
            ll cnt = 0;
            while(N%P[i] == 0){
                cnt++;
                N/=P[i];
            }
            g = gcd(g,cnt);
        }
    }
    if(N>1) g = gcd(g,1);

    if(tag == -1){ //如果是奇数
        while(g%2 == 0){
            g/=2;
        }
    }
    return g;
}
int main(){
    init();
    cin>>T;
    int kase = 0;
    while (T--){
        scanf("%lld",&N);
        printf("Case %d: %lld\n",++kase,solve());
    }

    return 0;
}