阶乘某题，用到了质因数分解和二分

链接：https://ac.nowcoder.com/acm/problem/204433
来源：牛客网
看的某大佬的才懂https://blog.nowcoder.net/n/aa5ff9efa80440c897a9aaae4401a467?f=comment
给定一个正整数 {p}p
求一个最小的正整数 {n}n，使得 {n!}n! 是 {p}p 的倍数
输入描述:
第一行输入一个正整数{T}T表示测试数据组数
接下来{T}T行，每行一个正整数{p}p
输出描述:
输出{T}T行，对于每组测试数据输出满足条件的最小的{n}n
示例1
输入
复制
4
1
2
4
8
输出
复制
1
2
4
4
//这道题的关键是求出最小的且是阶乘的一个数
对于p我们需要对他进行质因数分解，也就是每一个数都能化成几个质因数相乘，然后再二分答案
而二分的时候，判断条件很重要：
判断条件也就是从，如假设二分时mid=5，而我们要找的时14的倍数，首先14分解成2*7，而且我们需要开数组存质因数和它对应的数量num。
然后就是代码的判断部分

bool judge(int x)
{
    for(int i=1;i<=k;i++)
    {
        int sum=0;
        int pp=x;
        while(pp)
        {
            sum+=pp/primer[i];
            pp/=primer[i];
        }
        if(sum<num[i]) return false;
    }
    return true;
}

我们需要从中找到如5！（mid=5）中是二的倍数的有2 4（指12345中的2 4） 然后通过这个就可以sun=2，然后sun>num(是1)，然后继续判断质因子7的时候可不可以，如果都大于对应的num，那么自然可以，自然是倍数
某阶乘如果含有某数的全部质因子，且数量大于等于那么它肯定是它的倍数啦

for(int i=2;i*i<=p;i++)
        {
            if(p%i==0) primer[++k]=i;
            while(p%i==0)
            {
                p/=i;
                num[k]++;
            }
        }

质因数分解部分

#include<bits/stdc++.h>
using namespace std;
int n;
const int N=1e5;
int primer[N],num[N];
int k=0;
bool judge(int x)
{
    for(int i=1;i<=k;i++)
    {
        int sum=0;
        int pp=x;
        while(pp)
        {
            sum+=pp/primer[i];
            pp/=primer[i];
        }
        if(sum<num[i]) return false;
    }
    return true;
}
int main()
{
    cin>>n;
    while(n--)
    {
        memset(num,0, sizeof(num));//duo'c
        int p;
        cin>>p;
        k=0;
        for(int i=2;i*i<=p;i++)
        {
            if(p%i==0) primer[++k]=i;
            while(p%i==0)
            {
                p/=i;
                num[k]++;
            }
        }
        if(p>1) primer[++k]=p,num[k]++;
        int l=1,r=1e9+2,ans;//从1开始
        while(l<r)
        {
            int mid=l+r>>1;
            if(judge(mid))  r=mid,ans=mid;
            else l=mid+1;
        }
        cout<<ans<<endl;
    }
    return 0;
}