阶乘+二分( n! 是 p的倍数，最小的n)

链接：https://ac.nowcoder.com/acm/contest/4784/B
来源：牛客网

解析链接：

给定一个正整数 p
求一个最小的正整数 n，使得 n! 是 p的倍数

输入描述:

第一行输入一个正整数T表示测试数据组数
接下来T行，每行一个正整数p

输出描述:

输出T{行，对于每组测试数据输出满足条件的最小的n

示例1

输入

复制 4 1 2 4 8

4
1
2
4
8

输出

复制 1 2 4 4

1
2
4
4

备注:

T≤1e3,p≤1e9
解析：我们发现符合要求的N是单调递增的，就是如果N符合要求，那么N+1也一定符合要求，所以可以用二分 
我们可以将p进行分解质因子，并且要记录p分解的这个质因子的个数，对于每一个质因子，枚举N看看N中右几个is_prime[i]的
个数，如果小于则不行，如果都大于着是一个合理的解

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn=1e6+100;
int pp[maxn];
int num[maxn];
int k=0;
void inint(ll p){
    for(int i=2;i*i<=p;i++){
        if(p%i==0){
            pp[++k]=i;
            while(p%i==0){
                num[k]++;
                p/=i; 
            }
        }
    }
    if(p>1){
        pp[++k]=p;
        num[k]++;
    }
    return ;
}
int judge(int x){
    for(int i=1;i<=k;i++){
        int n=x;
        int z=0;
        while(n){
            z+=n/pp[i];
            n/=pp[i];
        }
        if(z<num[i]){
            return 0;
        }
    }
    return 1;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        ll p;
        cin>>p; 
        inint(p);
        int l=1,r=1e9;
        int ans;
        while(r>=l){
            int mid=(l+r)/2;
            if(judge(mid)){
                r=mid-1;
                ans=mid;
            } 
            else{
                l=mid+1;
            }
        }
        memset(num,0,sizeof(num));
        cout<<ans<<endl;
    }
}