JZOJ 5791 阶乘 —— 因数

题目：https://jzoj.net/senior/#main/show/5791

题意：有n个正整数a[i]，设它们乘积为p，你可以给p乘上一个正整数q，使p*q刚好为正整数m的阶乘，求m的最小值。

对于10%的数据，n<=10
对于30%的数据，n<=1000
对于100%的数据，n<=100000，a[i]<=100000

首先，p * q = m!，也就是 p 是 m! 的一个因数；

把 p 质因数分解，那么 m! 的每个对应质因数的次数都 >= p 中对应质因数的次数；

不必乘出来 p，只要把每个 a[i] 质因数分解即可；

对于 m!，统计质因数的次数就是 cnt[i] += m / pri[i] , m /= pri[i]，证明之类的很好想啦。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int const maxn=1e5+,inf=1e9;

int n,a[maxn],p[maxn],ans,mx,pri[maxn],cnt;

bool ck(int x)

{

    if(x<mx)return ;

    for(int i=,t,tmp;i<=x&&i<=mx;i++)

    {

        if(!p[i])continue;

        t=; tmp=x;

        while(tmp)t+=tmp/i,tmp/=i;

        if(t<p[i]){/*printf("t=%d p[%d]=%d\n",t,i,p[i]);*/ return ;}

//        printf("x=%d t=%d p[%d]=%d\n",x,t,i,p[i]);

    }

    return ;

}

int main()

{

    freopen("factorial.in","r",stdin);

    freopen("factorial.out","w",stdout);

    scanf("%d",&n);

    for(int i=;i<=n;i++)

    {

        scanf("%d",&a[i]);

        for(int j=;j*j<=a[i];j++)

            while(a[i]%j==)p[j]++,a[i]/=j,mx=max(mx,j);

        if(a[i]>)p[a[i]]++; mx=max(mx,a[i]);

    }

    int l=,r=inf;

    while(l<=r)

    {

        int mid=((l+r)>>);

//        printf("l=%d r=%d mid=%d ck=%d\n",l,r,mid,ck(mid));

        if(ck(mid))ans=mid,r=mid-;

        else l=mid+;

    }

    printf("%d\n",ans);

    return ;

}