题意：给定一个k和k个数字，求最小的数字n使得n!是∑ai!的倍数。
思路：设cnt[ i ]表示包含素数i出现的数目。把∑ai！的每一个质数的指数求出来，然后二分判断n是否满足条件即可。
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<cmath> #include<map> #include<queue> #include<bitset> #include<vector> #include<string> #include<stack> #include<set> #define ll long long #define PI acos(-1.0) #define F first #define S second #define pb push_back #define debug(x); printf("***:%d ",x); #define des(x); printf("des:%s ",x+1); const ll INF=0x3f3f3f3f3f3f3f3f; const int inf=0x3f3f3f3f; const ll mod=1e9+7; using namespace std; const int N=1e6+5; const int M=1e7+5; ll s; ll cao; int k; ll cnt[M]; int f[M],prime[M],tot,ans; void oula() { //f[1]=1; for (int i=2; i<=1e7; i++) { if (!f[i]) { prime[++tot]=i; f[i]=i;//欧拉筛筛质数 } for (int j=1; j<=tot; j++) { if (i*prime[j]>1e7) break; f[i*prime[j]]=i; if (i%prime[j]==0) break; } } } bool check(ll x) { for(int i=1;i<=tot;i++) { ll temp=x; ll sum=0; while(temp) { temp/=prime[i];//求二分的数包含某一个质数的数目。 sum+=temp; } if(sum<cnt[prime[i]]) return false; } return true; } int main() { oula(); scanf("%d",&k); for(int i=1;i<=k;i++) { scanf("%lld",&cao); s+=cao; cnt[cao]++; } for(ll i=1e7;i>=2;i--) cnt[i]+=cnt[i+1];//例：如果是质数29，则29!还要加上31!,30!等里包含的29数目。 for(ll i=1e7;i>=2;i--) { cnt[i/f[i]]+=cnt[i];//求大数里包含的小质数数目。 if(i!=f[i]) cnt[f[i]]+=cnt[i]; } ll l=1,r=s; while(l<=r) { ll mid=l+r>>1; if(check(mid)) { r=mid-1; } else l=mid+1; } printf("%lld ",l); return 0; }