牛客挑战赛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);
}
}