← 返回题目列表

Codeforces · 1468/L

L. 素因数选择

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

假设您有一个 $$$k$$$ 整数序列 $$$A = [a_1, a_2, \dots , a_k]$$$,其中每个 $$$a_i \geq 2$$$。如果 $$$a_1$$$ 可被 $$$p_1$$$ 整除,$$$a_2$$$ 可被 $$$p_2$$$ 整除,则素数序列 $$$P = [p_1, p_2, \dots, p_k]$$$ 被称为适合序列 $$$A$$$,依此类推。

如果素数序列 $$$P$$$ 中没有唯一的整数,则该序列被称为友好的。

如果每个适合$$$A$$$的序列$$$P$$$也是友好的(即不存在适合$$$A$$$但不友好的序列$$$P$$$,则序列$$$A$$$被称为理想序列。例如,序列$$$[2, 4, 16]$$$是理想的,而序列$$$[2, 4, 6]$$$则不是理想的(存在序列$$$P = [2, 2, 3]$$$,适合$$$A$$$,但不友好)。

给你 $$$n$$$ 不同的整数 $$$x_1$$$, $$$x_2$$$, ..., $$$x_n$$$。你必须准确地选择其中的$$$k$$$,使它们形成一个理想的序列,否则就报告这是不可能的。请注意,不能多次选择整数。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq k \leq n \leq 1000$$$)。

第二行包含 $$$n$$$ 成对不同的整数 $$$x_1$$$, $$$x_2$$$, ..., $$$x_n$$$ ($$$2 \leq x_i \leq 10^{18}$$$)。

输出

如果不可能从 $$$x_1$$$、$$$x_2$$$、...、$$$x_n$$$ 中准确选择 $$$k$$$ 整数,使所选整数形成理想序列,则打印 $$$0$$$。

否则,打印 $$$k$$$ 成对不同的整数 - 所选理想序列的元素。如果有多个答案,请打印其中任何一个。

示例

输入 #1

3 3
2 4 6

输出 #1

0

输入 #2

3 3
2 4 16

输出 #2

2 4 16

输入 #3

4 3
2 4 6 16

输出 #3

2 4 16