CF1834E

CF1834E MEX of LCM
固定左端点向右遍历的话，lcm一定是单调不减的，且对于每一次增加都至少翻倍，容易发现最小好数的最大取值为 \(n^2\)，所以大于 \(n^2\) 的lcm不用考虑。这样的话对于每个固定的左端点，向右拓展区间最多得到 \(\log n\) 个不同的数。也就只需要计算 \(\log n\)次lcm。
考虑从右往左枚举左端点，记录会使lcm变大的数字下标，每次只需要计算这些数的lcm即可。可以用队列记录，把每一个计算出来的lcm放进set中维护，最后遍历set统计答案

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll t,n,a[300010];
ll q[300010],tt,qc[300010],tc;
set<ll> ans;
inline ll read()
{ll x = 0;char ch = getchar();while(ch<'0'||ch>'9') ch = getchar();while(ch>='0'&&ch<='9'){x = (x<<1)+(x<<3)+(ch^48);ch = getchar();}return x;
}
ll gcd(ll a,ll b)
{return b?gcd(b,a%b):a;
}
ll lcm(ll a,ll b)
{return a/gcd(a,b)*b;
}
int main()
{t = read();while(t--){n = read(); ans.clear(); tt = 0; tc = 0;for (int i = 1;i <= n;i++) a[i] = read();for (int i = n;i;i--){ll lm = a[i],tmp; tc = 0;ans.insert(lm);for (int j = tt;j;j--){tmp = lcm(lm,a[q[j]]);if (tmp != lm) qc[++tc] = q[j];lm = tmp;if (lm > n*n) break;ans.insert(lm);}qc[0] = i; tt = 0;for (int j = tc;j >= 0;j--) q[++tt] = qc[j];}ll res = 0;for (auto it : ans){if (it != res+1) break;else res++;}cout << res+1 << "\n";}
}