CF1148G.Gold Experience

Consider an undirected graph $G$ with $n$ vertices. There is a value $a_i$ in each vertex.

Two vertices $i$ and $j$ are connected with an edge if and only if $gcd(a_i, a_j) \gt 1$, where $gcd(x, y)$ denotes the greatest common divisor (GCD) of integers $x$ and $y$.

Consider a set of vertices. Let's call a vertex in this set fair if it is connected with an edge with all other vertices in this set.

You need to find a set of $k$ vertices (where $k$ is a given integer, $2 \cdot k \le n$) where all vertices are fair or all vertices are not fair. One can show that such a set always exists.

考虑一个包含 $n$ 个顶点的无向图 $G$。每个顶点 $i$ 上有一个值 $a_i$。

当且仅当 $\gcd(a_i, a_j) > 1$ 时，顶点 $i$ 与顶点 $j$ 之间存在一条边，其中 $\gcd(x, y)$ 表示整数 $x$ 与 $y$ 的最大公约数（GCD）。

考虑一组顶点。若该组中某个顶点与该组内其余所有顶点均通过边相连，则称该顶点为公平的（fair）。

你需要找出一个包含 $k$ 个顶点的集合（其中 $k$ 是给定的整数，满足 $2 \cdot k \le n$），使得该集合中所有顶点均为公平的，或所有顶点均不为公平的。可以证明，这样的集合总是存在的。

The first line contains integers $n$ and $k$ ($6 \leq 2 \cdot k \leq n \leq 10^5$) — the number of vertices and parameter $k$.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($2 \le a_i \le 10^7$) — the values in the vertices.

第一行包含两个整数 $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$）—— 表示各顶点上的数值。

Print exactly $k$ distinct integers — the indices of the vertices in the chosen set in any order.

恰好输出 $k$ 个互不相同的整数——即所选顶点集合中各顶点的索引（顺序任意）。

In the first test case, set ${2, 4, 5}$ is an example of set where no vertices are fair. The vertex $2$ does not share an edge with vertex $4$ since $gcd(15, 8) = 1$. The vertex $4$ does not share an edge with vertex $2$. The vertex $5$ does not share an edge with vertex $2$.

In the second test case, set ${8, 5, 6, 4}$ is an example of a set where all vertices are fair.

在第一个测试用例中，集合 $\{2, 4, 5\}$ 是一个不存在公平顶点的集合示例。顶点 $2$ 与顶点 $4$ 之间没有边相连，因为 $\gcd(15, 8) = 1$；顶点 $4$ 与顶点 $2$ 之间也没有边相连；顶点 $5$ 与顶点 $2$ 之间同样没有边相连。

在第二个测试用例中，集合 $\{8, 5, 6, 4\}$ 是一个所有顶点均为公平顶点的集合示例。