阶乘_牛客博客

链接：

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

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

输入描述:

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

输出描述:

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

示例1
输入

输出

备注:
T≤10^3^,p≤10^9^
题解：
两个方法：
二分与贪心

在什么条件下n!会是p的倍数呢？
n!的素因子集合包含p的素因子集合，也就是对于每个质因子，阶乘n中的数量大于对应p中的数量

贪心：

暴力做法，从2开始循环质因数，对于每次一个质因数i，看p1当前能分解出多少个，然后再枚举n,看n最小为多少能做到质因数i的数量大于等于p1
代码中有句sum=max(sum,j);什么含义？你想如果我们之前求出n=9包含3的数量满足条件，那枚举5时得到n=10，10的阶乘是包含9的阶乘，也就是10！既满足质因数2也满足3，所以求最大max
代码内也有注释

代码：

#include<bits/stdc++.h>
using namespace std;
int main() {
    int t,p1,sum=0;
    cin>>t;
    while(t--) 
    {
        cin>>p1;
        sum=0;
        for(int i=2;i*i<=p1;++i)
         if(p1%i==0) 
         {
            int cnt=0;
            while(p1%i==0) 
            {
                p1/=i;
                ++cnt;
            }//当前质因子i在p1中的数量 
            int tmp=0;
            int j;
            for(j=i;;j+=i) 
            {
                     int n=j;
                    while(n%i==0)
                    {
                        n/=i;
                        ++tmp;
                    } //记录当前质因数在n中的数量 

                if(tmp>=cnt) break;//找到一个数，使得他的质因数i的数量多于等于p1 
            }
            sum=max(sum,j); 
 //           cout<<sum<<endl;
        }
        cout<<max(sum,p1)<<endl;
    }
}

二分：

其实就是把方法一中暴力的过程改成更为巧妙的二分过程，先将p1的质因数存入数组prime，然后二分查找，寻找最小的n，满足他的质因数i的数量多于等于p1
代码借鉴其大佬博客写的

代码：

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 3;
int prime[maxn], cnt[maxn], len = 0;
//素因子，素因子的个数，数组长度

int judge(int mid) {
    for (int i = 1; i <= len; i++)
    {
        int n = mid
        int sum = 0;
        while (n) 
        {
            sum += n / prime[i];
            n /= prime[i];
        }
        if (sum < cnt[i]) return 0;//不满足条件就找下一个n 
    }
    return 1;//满足要求 
}
int main() {
    int T; 
    cin>>T;
    int l,r,sum; 
    while (T--) 
    {
        int p1;
        cin>>p1;
        len = 0;
        memset(cnt, 0, sizeof cnt);
        for (int i = 2; i * i <= p1; i++)
        if ( p1 % i==0) 
        {
            prime[++len] = i;
            while (p1 % i==0) 
            {
                cnt[len]++;
                p1 /= i;
            }
        }
        if (p1 > 1) 
        {
            prime[++len] = p1;
            cnt[len]++;
        }
        //求出素因子及其个数
        l = 1, r = 1e9, sum = 0;
        while (l <= r) {
            int mid = l + r >> 1;
            if (judge(mid)) 
            {
                r = mid - 1;
                sum = mid;
            }
            else l = mid + 1; 
        }
        //二分查找
        printf("%d\n", sum);
    }
    return 0;
}