牛客小白月赛23B——阶乘

网址：https://ac.nowcoder.com/acm/contest/4784/B

题目描述

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

输入描述:

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

输出描述:

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

输入

4
1
2
4
8

输出

1
2
4
4

备注:

T<=10^3, p<=10^9

题解：

引用：https://www.cnblogs.com/Kanoon/p/12543390.html
先将p质因子分解，记录质因子a(i)以及这个质因子的次数b(i)。
然后二分枚举n，假设当前二分到的是mid。
遍历p的质因子，假设当前质因子为a(i)，次数为b(i)，就判断mid的阶乘中是否能分解出不少于b(i)个a(i)

AC代码：

#include<iostream>
#include<cstring>
using namespace std;
int a[100],b[100]={0},len=0;
int Cal(int mid,int x){
    int ans=0;
     //原理是n!中,x,2x,3x...mx,是x的倍数,那么先从这些数中，每个都拿出一个x,
    //那么就一共拿出n/x个x来，然后原先中最大的就是n/x,再如此循环 
    while(mid>=x){
        ans+=mid/x;
        mid/=x;
    }
    return ans;
}
bool Check(int mid){
    for(int i=0;i<=len;i++){
       //这里需要理解mid！中拿出num个a[i]来，并不影响后面a[i]拿出 
    if(Cal(mid,a[i])<b[i]) return false;
    }
    return true;
} 
int main(){
    int t,p;
    cin>>t;
    while(t--){
        cin>>p;
        if(p==1){
            cout<<1<<endl;
            continue;
        }
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        len=0;
        //这里只需要i从2开始递增，如果i增长到了一个合数i1，则此时的p一定不是i的倍数
        //因为p既然是合数，那么i从2开始递增，一定会遇到i1的的因数i2，那么在i是i2的时候，
        //p已经除以i2了，所以i1不可能是此时p的因数
        //这一块的复杂度只是(根号下p),至于里面的while循环，最多进行(logp),假设因数全是2，如果
        //还有别的因数，那么复杂度就会更小 
        for(int i=2;i*i<=p;i++){//a：存储p的所有质因子;b:每种质因子的个数
            if(p%i==0){
                while(p%i==0){
                    a[len]=i;
                    b[len]++;
                    p/=i;
                }
                len++;
            }
        }
        if(p>1)
        a[len]=p,b[len]=1;
        else len--;
        int l=1,r=1000000000;
        int ans=0; 
        while(l<=r){
            int mid=(l+r)/2;
            if(Check(mid)) ans=mid,r=mid-1;
            else l=mid+1; 
        } 
        cout<<ans<<endl;
    }
    return 0;
} 

打卡第11天。滴水穿石，付出终有回报。