牛客挑战赛46 B 最小的指数

给出一个数(x)，将它分解质因数成(prod p_i^{a_i}(a_i>0))，求(min(a_i))。

(Tle 10^5)

(xle 10^{18})

pollard-rho显然过不去。

先将(4000)以内的质数都暴力做一遍，如果遇到了(x)的因数计算一下。

对于剩余的质数，(ans)不会大于等于(5)，因为(4000^5>10^{18})。

那么(ansin {4,3,2,1})，分别判一下答案是不是完全(ans)次方数即可。

可以证明没有(ansge 2)并且(x)不是完全(ans)次方数的情况：发现这个情况下，(x)至少可以表示成(p_1^2p_2^3)的形式。这时候已经超过了范围。

时间复杂度(O(T|4000以内质数|))

using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define ll long long
#define N 4005
ll n;
int p[N],np;
bool inp[N];
ll qpow(ll x,ll y){
	ll r=1;
	for (;y;y>>=1,x=x*x)
		if (y&1)
			r=r*x;
	return r;
}
bool check(ll n,int k){
	ll x=pow(n,1.0/k);
	return qpow(x-1,k)==n || qpow(x,k)==n || qpow(x+1,k)==n;
}
void initp(int n){
	for (int i=2;i<=n;++i){
		if (!inp[i])
			p[++np]=i;
		for (int j=1;j<=np && i*p[j]<=n;++j){
			inp[i*p[j]]=1;
			if (i%p[j]==0)
				break;
		}
	}
}
ll m;
bool part1(){
	for (int i=1;i<=np;++i){
		if (n%p[i]==0){
			ll k=0;
			while (n%p[i]==0)
				++k,n/=p[i];
			m=min(m,k);
		}
	}
	return n==1;
}
ll part2(){
	if (check(n,4))
		return 4;
	if (check(n,3))
		return 3;
	if (check(n,2))
		return 2;
	return 1;
}
int main(){
	freopen("in.txt","r",stdin);
	initp(4000);
	int T;
	scanf("%d",&T);
	while (T--){
		scanf("%lld",&n);
		if (n==1){
			printf("0
");
			continue;
		}
		m=100;
		if (!part1())
			m=min(m,part2());
		printf("%lld
",m);
	}
	return 0;
}