← 返回题目列表

Codeforces · 1148/G

G. 黄金经验

中文机器翻译题面 查看原题

考虑一个具有 $$$n$$$ 顶点的无向图 $$$G$$$。每个顶点都有一个值$$$a_i$$$。

两个顶点 $$$i$$$ 和 $$$j$$$ 通过边连接当且仅当 $$$gcd(a_i, a_j) > 1$$$,其中 $$$gcd(x, y)$$$ 表示整数 $$$x$$$ 和 $$$y$$$ 的最大公约数 (GCD)。

考虑一组顶点。如果该集合中的某个顶点与该集合中所有其他顶点的边相连,我们称该顶点为公平的。

您需要找到一组 $$$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$$$ 个不同的整数 - 所选集合中顶点的索引(按任意顺序)。

示例

输入 #1

6 3
6 15 10 8 14 12

输出 #1

1 3 6

输入 #2

8 4
11 15 10 6 21 15 10 6

输出 #2

1 2 3 4

输入 #3

10 5
3003 17017 3230 49742 546 41990 17765 570 21945 36465

输出 #3

4 6 9 10 1

注意

在第一个测试用例中,集合 $$$\{2, 4, 5\}$$$ 是集合中没有公平顶点的示例。由于 $$$gcd(15, 8) = 1$$$,顶点 $$$2$$$ 不与顶点 $$$4$$$ 共享边。顶点 $$$4$$$ 不与顶点 $$$2$$$ 共享边。顶点 $$$5$$$ 不与顶点 $$$2$$$ 共享边。

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