description
给定一个长度为 \(n\) 的序列 \(a\)，求一个最小的正整数 \(x\)，使得它不是这个序列任意区间的最小公倍数。
值域 \(W=10^9\)
solution
显然答案最大的数量级为 \(O(n\log n)\)，记 \(m=n\times (\lfloor\log_2n\rfloor+1)\)。
考虑枚举区间右端点，维护以 \(r\) 为右端点的所有区间的最小公倍数集合,维护方式如下:
-
假设已经求出以 \(r-1\) 为右端点的所有区间的最小公倍数集合 \(S\)，那么 \(\forall k\in S\)，将 \(\mathrm{lcm} (a[r],k)\) 插入所求集合 \(T\)。
-
再将 \(a[r]\) 插入所求集合 \(T\)。
-
然后将 \(T\) 排序去重。
这样我们就可以对 \(T\) 中 \(\leq m\) 的元素打标记，枚举完所有右端点后找一下 mex 即可。
下面来说明对于任意右端点 \(r\)，\(|T|=O(\log W)\)。
假设 \(|S|=O(\log W)\)
可以发现，随着左端点 \(l\) 递减，\([l,r]\) 的 lcm 递增，且 \(\forall x_i,x_j\in T\)，若 \(x_i<x_j\)，则一定有 \(x_i\mid x_j\)。又因为 \(T\) 去过重，\(2\leq \dfrac{x_j}{x_i}\)，进一步不难得出 \(|T|=O(\log W)\)。
归纳可知，\(\forall r,|T|=O(\log W)\)
时间复杂度 \(O(n\log n)\) （实现的时候 \(>m\) 的元素直接扔掉，进一步把集合大小降到 \(O(\log n)\)）。
hint
多测清空注意复杂度。
这个题的关键在发现 \(|T|=O(\log W)\)。