cf1834E
首先可以估计一下答案的量级,因为小于答案的质数都要必须要出现,5e6以内的质数大概就是3e5,所以答案不超过5e6。
我们维护以i右端点的lcm的值,这些值的数量不会太多,因为每次增长都至少×2,所以是log级别。
每次新加的时候记得更新和去重即可。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<ctime>
#include<unordered_map>
#define A puts("YES")
#define B puts("NO")
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
//typedef __int128 i128;
typedef double db;
typedef long long ll;
const ll inf=1ll<<60;
const int N=3e5+5;
const int M=5e6+5;
ll a[N],n,b[N],tot;
int vis[M];
ll gcd(ll a,ll b){
if (!b) return a;
return gcd(b,a%b);
}
ll lcm(ll a,ll b){
return a/gcd(a,b)*b;
}
int main()
{
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
int zz;
scanf("%d",&zz);
for (int T=1;T<=zz;T++){
scanf("%lld",&n);
fo(i,1,n) scanf("%lld",&a[i]);
if (a[1]<=M) vis[a[1]]=T;
b[tot=1]=a[1];
fo(i,2,n) {
fo(j,1,tot) {
b[j]=lcm(b[j], a[i]);
}
fd(j,tot,1) {
b[j+1]=b[j];
}
++tot;
b[1]=a[i];
int m=unique(b+1,b+tot+1)-(b+1);
tot=m;
while (b[tot]>M && tot) tot--;
fo(j,1,tot) {
vis[b[j]]=T;
}
}
fo(i,1,M) if (vis[i]!=T) {
printf("%lld\n",i);
break;
}
}
return 0;
}