#define int long long #define endl '\n' using namespace std; int n,t,a[1000000]; map<int,int> c; signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>t; while(t--){ cin>>n; c.clear(); for(int i=1;i<=n;i++){ cin>>a[i]; } vector s,b; for(int i=1;i<=n;i++){ b.clear(); if(a[i]<=10000){ c[a[i]]=1; b.push_back(a[i]); } for(auto v:s){ int l=v*a[i]/__gcd(v,a[i]); if(l>10000)break; c[l]=1; if(b.empty()||b.back()!=1)b.push_back(l); } s.swap(b); } int ans=1; while(ans<=10000&&c[ans])ans++; cout<<ans<<endl; }

return 0;

}

幽默数

容易发现，在左端点固定的时候，若右端点向右移动，则区间的 $\text{lcm}$ 值要么不变，要么至少乘以 $2$。而对于一个质数，它不可能成为任意两个与它不等的数的 $\text{lcm}$，而第 $3 \times 10^5 + 1$ 个质数是 $4256233$，所以在所有区间的 $\text{lcm}$ 中，那些大于 $4256233$ 的是没有用的。

因此，记 $V = 4256233$，则当左端点固定的时候，不同的有用 $\text{lcm}$ 只有 $\log V$ 个。

考虑从右向左移动左端点，并且维护以当前点为左端点的不同 $\text{lcm}$。具体地，可以用两个集合 $A, B$ 分别维护当前存在的不同 $\text{lcm}$ 和所有可能有用的 $\text{lcm}$。左端点左移到 $i$ 的时候，需要将 $a_i$ 放入 $A$，并遍历 $A$ 中本来就存在的区间，对 $a_i$ 取 $\text{lcm}$ 后重新放入 $A$。每次更新完之后，就把当前 $A$ 中的元素放入 $B$ 中。最后对 $B$ 中的元素求 $\text{mex}$ 即可。

时间复杂度 $O(n \log^2 V)$。

#define int long long
#define endl '\n'
using namespace std;
int n,t,a[1000000];
map<int,int> c;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>t;
	while(t--){
		cin>>n;
		c.clear();
		for(int i=1;i<=n;i++){
			cin>>a[i];
		}
		vector<int> s,b;
		for(int i=1;i<=n;i++){
			b.clear();
			if(a[i]<=10000){
				c[a[i]]=1;
				b.push_back(a[i]);
			}
			for(auto v:s){
				int l=v*a[i]/__gcd(v,a[i]);
				if(l>10000)break;
				c[l]=1;
				if(b.empty()||b.back()!=1)b.push_back(l);
			}
			s.swap(b);
		}
		int ans=1;
		while(ans<=10000&&c[ans])ans++;
		cout<<ans<<endl;
	}
	
	return 0;
}