描述 有n个正整数a[i]，设它们乘积为p，你可以给p乘上一个正整数q，使pq刚好为正整数m的阶乘，求m的最小值。 输入 共两行。 第一行一个正整数n。 第二行n个正整数a[i]。 输出 共一行 一个正整数m。 样例输入 1 6 样例输出 3 提示 样例解释： 当p=6，q=1时，pq=3！ 【数据范围与约定】 对于10%的数据，n<=10 对于30%的数据，n<=1000 对于100%的数据，n<=100000，a[i]<=100000
我们可以二分m，m是具有单调性的
考虑如何check
显然只要这个m分解质因数过后，每个因子的个数大于等于原有的因子就是可行的
我们回到一个问题 如何快速求出一个数内所含的各个质数的个数
假设要求27中所含3的个数
27！=1*2*...*27 包含 1 个 3 的数有 27/(3^1)=9 个 包含 2 个 3 的数有 27/(3^2)=3 个 包含 3 个 3 的数有 27/(3^3)=1 个 总共：9+3+1=13 个 所以 27！里面有 13 个 3 相乘。这样就可以求出来了qwq
#include<bits/stdc++.h> #define N 100005 using namespace std; int n,prime[N],big[N],cnt,tong[N],a[N]; bool is[N]; int pm; inline void Pick(int n) { is[0]=is[1]=1; //1代表不是 for(int i=2;i<=n;i++) { if(is[i]==0) { prime[++cnt]=i; //没标记到（是素数） big[i]=i; } for(int j=1;j<=cnt&&i*prime[j]<=n;j++) //枚举前面所有素数 { is[i*prime[j]]=1; //标记前面素数的倍数 big[i*prime[j]]=big[i]; if((i%prime[j])==0) break; //如果不是最小质因子 就退出 } } } void split(int x) { while(x>1) { if (big[x]>pm) pm=big[x]; tong[big[x]]++; x/=big[x]; } } inline bool check(int x) { for(int i=1;i<=pm;i++) { if (is[i]) continue; int temp=i; int cur=0; while(temp<=x) { cur+=(x/temp); temp*=i; } if(cur<tong[i]) return false; } return true; } int main() { ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); Pick(100000); cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; split(a[i]); } int l=pm,r=1e9; while(l<r) { int m=(l+r)/2; if(check(m)) r=m; else l=m+1; } cout<<l; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9745053.html
相关资源：各显卡算力对照表！