CF1483B Playlist

Arkady 有一个播放列表，最初包含 $n$ 首歌曲，按它们在播放列表中出现的顺序从 $1$ 到 $n$ 编号。Arkady 从第 $1$ 首歌开始，依次听播放列表中的歌曲。播放列表是循环的，也就是说，在听完最后一首歌后，Arkady 会从头开始继续听。 每首歌有一个类型 $a_i$，是一个正整数。假设 Arkady 听完类型为 $y$ 的歌曲，上一首听的是类型为 $x$ 的歌曲。如果 $\operatorname{gcd}(x, y) = 1$，他会把刚听完的那首（类型为 $y$）从播放列表中删除。之后他会正常继续听歌，跳过已删除的歌曲，并且忘记之前听过的所有歌曲。换句话说，删除一首歌后，他不能立刻删除下一首歌。 这里 $\operatorname{gcd}(x, y)$ 表示整数 $x$ 和 $y$ 的最大公约数。 例如，如果初始歌曲类型为 $[5, 9, 2, 10, 15]$，那么播放列表的变化如下： \[ 5, 9, 2, 10, 15 \to 5, 9, 2, 10, 15 \to 5, 2, 10, 15 \] （因为 $\operatorname{gcd}(5, 9) = 1$） \[ \to 5, 2, 10, 15 \to 5, 2, 10, 15 \to 5, 2, 10, 15 \to 5, 2, 10, 15 \to 5, 2, 10, 15 \to 5, 10, 15 \] （因为 $\operatorname{gcd}(5, 2) = 1$） \[ \to 5, 10, 15 \to 5, 10, 15 \to \ldots \] 加粗的数字表示最近两首播放的歌曲。注意，每当一首歌被删除后，Arkady 会忘记之前听过的所有歌曲。 给定初始播放列表，请你确定最终会被删除的歌曲编号，以及它们被删除的顺序。

每个测试包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 10\,000$）。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示歌曲数量。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$），表示每首歌的类型。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每个测试用例，输出一行。首先输出一个整数 $k$，表示被删除的歌曲数量。接着输出 $k$ 个不同的整数，表示被删除的歌曲编号，顺序为它们被删除的顺序。

第一个测试用例的解释见题面。 第二个测试用例，播放列表变化如下： \[ 1, 2, 4, 2, 4, 2 \to 1, 2, 4, 2, 4, 2 \to 1, 4, 2, 4, 2 \] （因为 $\operatorname{gcd}(1, 2) = 1$） \[ \to 1, 4, 2, 4, 2 \to 1, 4, 2, 4, 2 \to 1, 4, 2, 4, 2 \to 1, 4, 2, 4, 2 \to 1, 4, 2, 4, 2 \to 4, 2, 4, 2 \] （因为 $\operatorname{gcd}(2, 1) = 1$） \[ \to 4, 2, 4, 2 \to \ldots \] 第三个测试用例，播放列表变化如下： \[ 1, 2 \to 1, 2 \to 1 \] （因为 $\operatorname{gcd}(1, 2) = 1$） \[ \to 1 \to 1 \] （Arkady 连续两次听同一首歌） \[ \to \] （因为 $\operatorname{gcd}(1, 1) = 1$） 第四个测试用例与第三个测试用例在删除第二首歌后相同。 第五个测试用例，反复听同一首歌，但由于 $\operatorname{gcd}(2, 2) \ne 1$，所以不会被删除。 由 ChatGPT 4.1 翻译