CF1148G Gold Experience

给定一个无向图 $G$，该图有 $n$ 个顶点。每个顶点上有一个值 $a_i$。 当且仅当 $\gcd(a_i, a_j) > 1$ 时，顶点 $i$ 和顶点 $j$ 之间有一条边，其中 $\gcd(x, y)$ 表示整数 $x$ 和 $y$ 的最大公约数。 考虑一个顶点集合。如果集合中的某个顶点与该集合中的所有其他顶点都有边相连，则称该顶点是“公平的”。 你需要找到一个包含 $k$ 个顶点的集合（其中 $k$ 是给定的整数，且 $2 \cdot k \le n$），使得集合中的所有顶点要么全是公平的，要么全都不是公平的。可以证明，总能找到这样的集合。

第一行包含两个整数 $n$ 和 $k$（$6 \leq 2 \cdot k \leq n \leq 10^5$），分别表示顶点数和参数 $k$。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$2 \le a_i \le 10^7$），表示每个顶点上的值。

输出恰好 $k$ 个不同的整数，表示所选顶点的编号，顺序任意。

在第一个测试用例中，集合 $\{2, 4, 5\}$ 是一个所有顶点都不是公平顶点的例子。顶点 $2$ 与顶点 $4$ 没有边，因为 $\gcd(15, 8) = 1$。顶点 $4$ 与顶点 $2$ 也没有边。顶点 $5$ 与顶点 $2$ 也没有边。 在第二个测试用例中，集合 $\{8, 5, 6, 4\}$ 是一个所有顶点都是公平顶点的例子。 由 ChatGPT 4.1 翻译