双log过了

显然可以二分答案 对前k个质数依次验证 然后就有了双log做法 但是应该会T

发动人类智慧 考虑如何减少单次判定的时间

我们发现，当二分左端点右移的时候 会添加一段使得判定条件更容易被满足的部分 并且这一部分不会被删掉

这一部分的影响就是 会使得一部分数在后续的二分中一定合法 我们可以在后续判定时跳过他们

但是这样会使得我们无法获得"在判定不合法后return"所带来的常数优化 因此这里我采用类似当前弧优化的方法 记录st（start）表示st之前的都一定合法 每次从st开始判定即可

代码：

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define F first
#define S second
#define mkp make_pair 
using namespace std;
const int inf=1e18;
int T,k,a[110];
const int N=1e6,E=1e4,V=1e18;
bitset<N+E>pvis;
int pri[N/10+E],ptot;
int st;
int OK(int x){
	for(int i=st;i<=k;i++){
		int ss=pri[i],cnt=0;
		while(ss<=x){
			cnt=cnt+x/ss;
			if(ss>V/pri[i]) break;
			ss=ss*pri[i];
		}
		if(cnt<a[i]){
			st=i;
			return 0;
		} 
	}return 1;
}
signed main() {
	for(int i=2;i<=N;i++){
		if(pvis[i]==0){
			pri[++ptot]=i;
		}
		for(int j=1;j<=ptot&&pri[j]*i<=N;j++){
			pvis[i*pri[j]]=1;
			if(i%pri[j]==0) break;
		}
	}
	ios::sync_with_stdio(0);
	cin.tie(0);
//	freopen("ex.in","r",stdin);
//	freopen("my.out","w",stdout);
//	system("fc my.out ex.out");return 0;
	cin>>T;
	while(T--){
		cin>>k;
		for(int i=1;i<=k;i++){
			cin>>a[i];
		}
		int l=1,r=V;
		st=1;
		while(l<r){
			int mid=(l+r)/2;
			if(OK(mid)) r=mid;
			else l=mid+1;
		}cout<<l<<"\n";
	}
	return 0;
}

优化思路详见zhengtDL（具体实现稍微有点区别）

温馨提示：先枚举质数p，再二分答案，可能 会更快一点哦

#include<bits/stdc++.h>
using namespace std;
char buf[1<<20],*p1,*p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
inline long long rd(){
	long long x=0;int f=1;char c=gc();
	for(;c<'0'||'9'<c;c=gc()) if(c=='-') f=-1;
	for(;'0'<=c&&c<='9';c=gc()) x=(x<<3)+(x<<1)+(c^48);
	return x*f;
}
inline void wt(long long x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) wt(x/10);
	putchar('0'+x%10);
}
int n=600,m,prime[2005];
bitset<2005> not_prime;
void euler(){
	for(int i=2;i<=n;i++){
		if(!not_prime[i]){
			prime[++m]=i;
		}
		for(int j=1;j<=m&&i*prime[j]<=n;j++){
			not_prime[prime[j]*i]=1;
			if(!(i%prime[j])) break;
		}
	}
}
bool check(long long x,int p,long long ct){
	long long cnt=0;
	for(int i=1;i<=ct&&x;i++){
		x/=p;cnt+=x;
		if(cnt>=ct) return 1;
	}return 0;
}
int T,K;
long long c[105];
long long ans;
const long long INF=0x7f7f7f7f7f7f7f7f;
//const __int128 INF=INF1*INF1;
int main()
{
//	wt(INF);putchar('\n');
	euler();
//	cout<<m<<'\n';
	T=rd();
	while(T--){
		ans=1;
		K=rd();
		for(int i=1;i<=K;i++) c[i]=rd();
		for(int i=1;i<=K;i++){
			long long l=ans,r=INF,mid,ans1=0;
			if(check(l,prime[i],c[i])) continue;
			while(l<=r){
				mid=((r-l)>>1)+l;
				if(check(mid,prime[i],c[i])) r=mid-1,ans1=mid;
				else l=mid+1;
			}
			ans=max(ans,ans1);
		}
		wt(ans);putchar('\n');
	}
	return 0;
 } 

loj#530. 「LibreOJ β Round #5」最小倍数

注意到 $m$ 给出了质因数分解形式

不难看出，所有满足条件的 $x$ ，一定对于所有的 $i$ 满足 $x!\ mod\ p_i^{c_i}=0$

所以我们就可以对于每一个 $c_i$ ，求出满足$x!\ mod\ p_i^{c_i}=0$的最小的 $x$ ，记为 $x_i$ ，那么答案就是 $x_i max$

可以用类似于倍增的方式求，先预处理出 $st_{i,j}$表示一个质数 $p_i$ 在$p_i ^j!$的唯一分解中的指数，递推式为 $st_{i,j}=st_{p,j-1} \cdot p + 1$，之后就可以对于每个 $k$ 从大到小遍历 $j$ ，如果存在正整数 $k$ 使得 $c_i ≥ k \cdot st[i][j]$ 那么便让 $c_i$ 减去 $k \cdot st[i][j]$ ，并让答案加上 $k \cdot p_i ^j$，（其实就是把 $x$ 拆成 $p$ 进制，再利用阶乘的性质得出 $x!$ 的唯一分解中 $p$ 上面的指数，只不过这里是反过来构造 $x$ ）。

下面是代码，复杂度不会证（，但跑的很快。

#include<bits/stdc++.h>
using namespace std;
const long long maxxxxx=1000000000000000000ll;
bool b[609];
int p[109],len=0,cnt[109];
long long a[109],st[109][71],fac[109][71];
int main(){
	b[1]=1;
	for(int i=2;len<100;i++){
		if(!b[i]) p[++len]=i;
		for(int j=1;i*p[j]<=550&&j<=len;j++){
			b[i*p[j]]=1;
			if(i%p[j]==0) break;
		}
	}
	for(int i=1;i<=100;i++)
		while(st[i][cnt[i]]<=maxxxxx){ 
			if(st[i][cnt[i]]>(maxxxxx-1)/p[i]) break;
			++cnt[i];
			st[i][cnt[i]]=st[i][cnt[i]-1]*p[i]+1;
		}
	for(int i=1;i<=100;i++){
		fac[i][0]=1;
		for(int j=1;j<=cnt[i];j++) fac[i][j]=fac[i][j-1]*p[i];
	}
	int T;
	scanf("%d",&T);
	while(T--){
		int k;
		long long sna=1;
		scanf("%d",&k);
		for(int i=1;i<=k;i++) scanf("%lld",&a[i]);
		for(int i=1;i<=k;i++){
			if(a[i]==0)
				continue;
			long long x=a[i],ans=0;
			int l=0,r=cnt[i];
			while(l+1<r){
				int mid=(l+r)>>1;
				if(st[i][mid]<=x) l=mid;
				else r=mid;
			}
			long long ffac=fac[i][l];
			for(int j=l;j>=1;j--){
				if(x>=st[i][j]){
					long long y=x/st[i][j];
					x-=y*st[i][j];
					ans+=y*ffac;
				}
				ffac/=p[i];
			}
			sna=max(sna,ans);
		}
		printf("%lld\n",sna);
	}
	return 0;
}