CF1482D 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 翻译