CF2258E DivMEX

给定一个正整数数组 $a_1, a_2, \ldots, a_n$。 定义 $f(l, r)$，其中 $1 \leq l \leq r \leq n$，表示最小的正整数，使得该整数不能整除 $\operatorname{lcm}(a_l, a_{l+1}, \ldots, a_r)$。这里，数组一段的 $\operatorname{lcm}$ 表示这些整数的最小公倍数。 请判断存在哪些正整数 $x$，使得存在某一对整数 $(l, r)$，满足 $1 \leq l \leq r \leq n$ 且 $f(l, r) = x$。

每个测试点包含多组测试用例。第一行包含整数 $t$（$1 \le t \le 10^4$），表示测试用例的组数。 每组测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示数组的长度。 第二行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$）。 保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出两行。 第一行输出一个整数 $k$，表示满足条件的整数 $x$ 的个数。 第二行输出 $k$ 个升序排列的整数 $x_1 < x_2 < \ldots < x_k$，表示所有满足条件的 $x$。

对于第一个测试用例，唯一的 $(l,r)$ 为 $(1,1)$，且 $f(1,1)=2$。 对于第二个测试用例，$(l,r)=(1,1)$ 得到的约数集合为 $\{1,2\}$，$(l,r)=(1,2)$ 得到的约数集合为 $\{ 1, 2, 3, 6\}$，$(l,r)=(2,2)$ 得到的约数集合为 $\{1, 3\}$。这意味着 $f(1,1)=3$，$f(1,2)=4$，$f(2,2)=2$。没有其他的 $(l,r)$ 会产生不同的 $f$ 值，所以答案为 $[2,3,4]$。 对于最后一个测试用例，有 $f(2,2)=2$，$f(1,1)=3$ 且 $f(1,5)=5$。可以看出没有其他可能的取值。 由 ChatGPT 5 翻译