CF1834E MEX of LCM
樱雪喵
·
·
题解
不会做 *2300。鉴定为没救了。
Description
给定长度为 n 的序列 a，求最小正整数 x，使得 x 不是 a 任何一个子段的 \operatorname{lcm}。
## Solution
考虑答案的上界，因为长度为 $n$ 的序列只有 $n^2$ 个子段，那么答案必然是不超过 $n^2$ 的。但实际答案的上界是 $n\log n$，我们将在随后给出证明。
固定当前区间的左端点 $l$，则在 $r$ 右移过程中，区间 $\operatorname{lcm}$ 显然不会变小，因此只有 **不变/变大** 两种情况。
对于 $\operatorname{lcm}$ 变大的情况，不难发现新的 $\operatorname{lcm}$ 一定是旧 $\operatorname{lcm}$ 的倍数。也就是说，每次变大，$\operatorname{lcm}$ 的值是至少翻倍的。又根据上文所述，当 $\operatorname{lcm}$ 增大到超过 $n^2$ 就已经不可能成为答案了，无需继续枚举。那么对于每个 $l$，有效的 $\operatorname{lcm}$ 只有 $\log n$ 个，证得答案的上界为 $n\log n$。
那么问题的瓶颈变成了：如何只枚举变大的位置的 $\operatorname{lcm}$ 值？
~~于是这只菜喵就不会了。~~
考虑倒序枚举 $l$，并维护上一轮所有出现过的 $\operatorname{lcm}$ 值。那么这一轮就只让 $a_l$ 对上一轮出现的所有值求 $\operatorname{lcm}$ 就好了。这个东西用 set 是容易维护的。
```cpp
#define int long long
const int N=3e5+5;
int n,a[N];
set<int> ans,s;
il int lcm(int x,int y) {return x/__gcd(x,y)*y;}
signed main()
{
int T=read();
while(T--)
{
n=read(); ans.clear(),s.clear();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=n;i;i--)
{
set<int> now;
for(auto x:s) if(lcm(x,a[i])<1e9) now.insert(lcm(x,a[i]));
now.insert(a[i]),swap(now,s);
for(auto x:s) ans.insert(x);
}
int lst=0,res=0;
for(auto x:ans)
if(x>lst+1) {res=lst+1;break;}
else lst=x;
printf("%lld\n",res?res:lst+1);
}
return 0;
}
```