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

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

传送门

题意:1e6次询问,每次给你一个1e18的数问你质因数分解后的所有质因数中的指数幂中最小的是多少。

题解:将4000以下的素数预处理,然后分解n,若剩余值等于1说明已完全分解,若大于1,也易知其剩余最小质因数指数幂不超过4,便如下分类讨论。

1.若为4,则必为x^4==n;

2.若为3,则必为x^3==n;

3.若为2,则必为x2==n或(a*b)2==n;

4.否则为1。

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
#define ll long long
const ll Maxn = 4e3;
ll prime[Maxn+7],t,n;
void solve() {
	memset(prime,0,sizeof(prime));
	for(int i = 2;i <= Maxn; i++) {
		if(!prime[i])prime[++prime[0]]=i;
		for(int j=1;j<=prime[0]&&prime[j]<=Maxn/i;j++){
			prime[prime[j]*i]=1;
			if(i%prime[j]==0)break;
		}
	}
}
int main(){
	solve();
	cin>>t;
	while(t--){
		scanf("%lld",&n);
		if(n==1){
			printf("0\n");
			continue;
		}
		ll ans=1e9,now;
		for(int i=1;i<=prime[0];i++){
			if(n%prime[i]==0){
				now=0;
				while(n%prime[i]==0){
					now++;
					n/=prime[i];
				}
				ans=min(ans,now);
			}
		}
		if(n!=1){
			ll lin4,lin3,lin2;
			lin2=(ll)sqrt(n);
			lin4=(ll)sqrt(lin2);
			lin3=(ll)(pow(n*1.0,1.0/3)+0.1);
			if(lin4*lin4*lin4*lin4==n){
				now=4;
			}
			else if(lin3*lin3*lin3==n){
				now=3;
			}
			else if(lin2*lin2==n){
				now=2;
			}
			else{
				now=1;
			}
			ans=min(now,ans);
		}
		printf("%lld\n",ans);
	}
}
上一篇:android进阶之光!46道面试题带你了解中高级Android面试,含泪整理面经


下一篇:46. 定义一个3行3列的二维数组,从键盘输入9个数的值。输出其中最大值和最小值及其所在的行列坐标。