P15542 [CCC 2026 S3] Common Card Choice

有 $N$ 张卡片，上面写着正整数。Alice 取走其中一些卡片，然后 Bob 从剩下的卡片中取走一些。两人都必须至少取一张卡片，且 Alice 不能取走所有卡片。然后 Alice 和 Bob 分别计算他们手中卡片上的数字之和。如果这两个和存在一个大于 1 的公因数，那么 Alice 和 Bob 就能获得一袋糖果；否则不能。给定桌上的卡片，判断 Alice 和 Bob 是否有可能获得糖果，如果可能，请给出一种取法。 更具挑战性的是，在某些情况下，Alice 和 Bob 都不知道任何卡片上的数值。 注意：整数 $d$ 是整数 $q$ 的 **因数** 是指 $q$ 除以 $d$ 没有余数。整数 $z$ 是整数 $x$ 和 $y$ 的 **公因数** 是指 $z$ 同时是 $x$ 和 $y$ 的因数。

第一行包含一个整数 $N$（$2 \le N \le 10^5$）。 第二行包含 $N$ 个整数 $c_i$（$1 \le c_i \le 10^{12}$）。

第一行输出 **YES** 如果可能得到糖果，否则输出 **NO**。 如果答案为 **YES**，则在第二行输出两个整数 $A$ 和 $B$，分别表示 Alice 和 Bob 应取的卡片数量，中间用一个空格隔开。第三行输出 $A$ 个空格分隔的数字，表示 Alice 所取卡片的索引。第四行输出 $B$ 个空格分隔的数字，表示 Bob 所取卡片的索引。如果有多种选取方式，输出任意一种。 如果输入属于最后一个子任务，则第一行输出一个整数 $K \le 100$，接下来输出 $K$ 组可能的组合，每组组合的格式与其他子任务中 **YES** 时的输出相同：一行包含 $A$ 和 $B$；一行包含 $A$ 个卡片索引；一行包含 $B$ 个卡片索引。所有猜测中的卡片索引必须互不相交，即每个卡片索引至多出现在一个猜测中。如果其中任意一种组合能使 Alice 和 Bob 获得糖果，你的输出将被判为正确。注意，在猜测之间你不会收到任何反馈。

#### 样例输入 1 的输出解释 Alice 的卡片之和为 $7 + 11 + 17 = 35$，Bob 的卡片之和为 $31 + 13 + 19 = 63$，$35$ 和 $63$ 都能被 $7$ 整除。 #### 样例输入 2 的输出解释 注意 $3$、$11$ 和 $17$ 没有公因数，并且这些数中任意两个的和（$14$、$20$、$28$）与剩下的第三个数都没有公因数。 #### 样例输入 3 的输出解释 总共给出了两个猜测。第一个猜测包含索引 $\{1\}$ 和 $\{3, 5\}$。第二个猜测包含索引 $\{100, 101, 102\}$ 和 $\{201, 200\}$。 注意所有索引集合互不相交。 尽管输出格式正确，但该输出将获得 **答案错误**，因为这两个猜测不足以让 Alice 和 Bob 获得一袋糖果。 下表展示了 15 分的分布情况： | 分值 | $N$ 的范围 | $c_i$ 的范围 | |:-:|:-:|:-:| | 2 分 | $2 \le N \le 3$ | $1 \le c_i \le 100$ | | 1 分 | $2 \le N \le 10$ | $1 \le c_i \le 100$ | | 1 分 | $2 \le N \le 10^5$ | $1 \le c_i \le 2$ | | 2 分 | $2 \le N \le 10^5$ | $1 \le c_i \le 10^5$ | | 2 分 | $2 \le N \le 10^5$ | $1 \le c_i \le 10^{12}$ | | 7 分 | $N = 10^5$ | $c_i = -1$，见下面的注释 | **注释**：对于最后一个子任务，你将得到 $N$，但所有 $N$ 张卡片的数值将被标记为 $-1$，表示这些卡片的值对你未知。在这个子任务中，总是存在一种 Alice 和 Bob 可以选取卡片的方式使得他们获得一袋糖果。 翻译由 DeepSeek 完成