有n个正整数a[i]，设它们乘积为p，你可以给p乘上一个正整数q，使p*q刚好为正整数m的阶乘，求m的最小值。
共两行。
第一行一个正整数n。
第二行n个正整数a[i]。
共一行
一个正整数m。
1
6
3
对于10%的数据，n<=10
对于30%的数据，n<=1000
对于100%的数据，n<=100000，a[i]<=100000
这是第几次被二分答案上界给neng死了。。。10分滚粗。。。
首先可以先将p分解质因数，可以推出最后m!一定是包含了p的所有质因子的。
所以就可以二分m的值（上界要设很大，否则如果出现100000个相同数（或类似这种情况），最后m值就会很大），判断一下是否包含p，如果可以就下调，否则上调。
#include<bits/stdc++.h> using namespace std; typedef long long LL; const LL maxn=100010; LL P[maxn],s1[maxn],s2[maxn]; LL tot,n,a,last; bitset<maxn> isprime; void pre() { isprime[0]=isprime[1]=1; for(LL i=2;i<=100000;++i) { if(!isprime[i]) { for(LL j=i+i;j<=maxn;j+=i) isprime[j]=1; P[++tot]=i; } } } LL check(LL x) { memset(s2,0,sizeof(s2)); for(LL i=1;P[i]<=x&&i<=tot;++i) { LL tmp=x; while(tmp) { tmp/=P[i]; s2[i]+=tmp; } } for(LL i=1;i<=last;++i) if(s1[i]>s2[i]) return false; return true; } void fj(LL x) { if(x==1||x==0) return; for(LL i=1;P[i]<=x&&i<=tot;++i) { while(x%P[i]==0) { x/=P[i]; s1[i]++; } last=max(last,i); } } int main() { pre(); scanf("%lld",&n); for(LL i=1;i<=n;++i) { scanf("%lld",&a); fj(a); } LL l=1,r=100000000000; while(l<r) { LL mid=l+r>>1; if(check(mid)) r=mid; else l=mid+1; } printf("%lld",l); return 0; }
原文：https://www.cnblogs.com/Ishtar/p/9745127.html