传送门 https://jzoj.net/senior/#main/show/5791
Description
有 n 个正整数 a[i], 设它们乘积为 p, 你可以给 p 乘上一个正整数 q, 使 p*q 刚好为正整数 m 的阶乘, 求 m 的最小值.
Input
共两行.
第一行一个正整数 n.
第二行 n 个正整数 a[i].
Output
共一行
一个正整数 m.
- Sample Input
- 1
- 6
- Sample Output
- 3
样例解释:
当 p=6,q=1 时, p*q=3!
Data Constraint
对于 10% 的数据, n<=10
对于 30% 的数据, n<=1000
对于 100% 的数据, n<=100000,a[i]<=100000
- Code
- //By Menteur_Hxy
- #pragma GCC diagnostic error "-std=c++11"
- #pragma GCC optimize("-fdelete-null-pointer-checks,inline-functions-called-once,-funsafe-loop-optimizations,-fexpensive-optimizations,-foptimize-sibling-calls,-ftree-switch-conversion,-finline-small-functions,inline-small-functions,-frerun-cse-after-loop,-fhoist-adjacent-loads,-findirect-inlining,-freorder-functions,no-stack-protector,-fpartial-inlining,-fsched-interblock,-fcse-follow-jumps,-fcse-skip-blocks,-falign-functions,-fstrict-overflow,-fstrict-aliasing,-fschedule-insns2,-ftree-tail-merge,inline-functions,-fschedule-insns,-freorder-blocks,-fwhole-program,-funroll-loops,-fthread-jumps,-fcrossjumping,-fcaller-saves,-fdevirtualize,-falign-labels,-falign-loops,-falign-jumps,unroll-loops,-fsched-spec,-ffast-math,Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2",3)
- #pragma GCC target("avx","sse2")
- #include<set>
- #include<map>
- #include<cmath>
- #include<cstdio>
- #include<vector>
- #include<cstdlib>
- #include<cstring>
- #include<iostream>
- #include<algorithm>
- #define int long long
- #define F(i,a,b) for(register int i=(a);i<=(b);i++)
- #define R(i,a,b) for(register int i=(b);i>=(a);i--)
- #define E(i,u) for(register int i=head[u];i;i=nxt[i])
- #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin)),p1==p2?EOF:*p1++)
- using namespace std;
- typedef long long LL;
- char buf[1<<21],*p1,*p2;
- inline int read() {
- int x=0,f=1; char c=getchar();
- while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}
- while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();
- return x*f;
- }
- const int N=100010;
- int n,tot,cnt;
- int pri[N],vis[N],mip[N],p[N],M[N];
- void resolve(int x) {
- while(mip[x]!=x) {
- if(!M[mip[x]]) p[++cnt]=mip[x];
- M[mip[x]]++; x/=mip[x];
- }
- if(mip[x]==x&&x!=1&&x!=0) {
- if(!M[mip[x]]) p[++cnt]=mip[x];
- M[mip[x]]++;
- }
- }
- bool jud(int x) {
- F(i,1,cnt) {
- int res=0,tmp=p[i];
- while(tmp<=x) res+=x/tmp,tmp*=p[i];
- if(res<M[p[i]]) return 0;
- } return 1;
- }
- void init() {
- mip[1]=1;
- F(i,2,100000) {
- if(!vis[i]) pri[++tot]=i,mip[i]=i;
- for(register int j=1;j<=tot&&i*pri[j]<=100000;j++) {
- vis[i*pri[j]]=1;
- mip[i*pri[j]]=pri[j];
- if(i%pri[j]==0) break;
- }
- }
- }
- signed main() {
- freopen("factorial.in","r",stdin);
- freopen("factorial.out","w",stdout);
- n=read();
- init();
- F(i,1,n) resolve(read());
- // jud(10);
- // F(i,1,cnt) cout<<p[i]<<" ";cout<<endl;
- int l=1,r=5e6;
- while(l<=r) {
- int mid=(l+r)>>1;
- if(jud(mid)) r=mid-1;
- else l=mid+1;
- // printf("%d\n",mid);
- }
- printf("%d",l);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2722751.html