Prime Divisors Selection

题意翻译

对于一个包含 $k$ 个数字的序列 $A=[a_1,a_2,...a_k]$，若一个仅包含 $k$ 个质数的序列 $P=[p_1,p_2,...,p_k]$ 满足对于所有整数 $i(1\leq i\leq k)$ 有 $p_i$ 是 $a_i$ 的因数，那么我们称这个序列 $P$ 就是序列 $A$ 的“合适”序列。 进一步的，我们称一个序列 $A$ 是“理想”序列仅当这个序列的任意“合适”序列都没有元素只出现一次，比如说序列 $[2,4,8]$ 是“理想”序列，因为他唯一的“合适”序列 $[2,2,2]$ 没有任何元素只出现一次，序列 $[4,6,8]$ 就不是“理想”序列，它有两个“合适”序列 $[2,2,2],[2,3,2]$,其中第二个“合适”序列里有一个唯一的元素 $3$。 现在给定长度为 $n$ 的初始序列 $X=[x_1,x_2,...,x_n]$ 和参数 $k$，你要选出 $X$ 当中的 $k$ 个元素，并组成一个“理想”序列，如果有解，输出这个序列（输出任意一个合法解即可），无解输出一个 $0$。 $1\leq k\leq n\leq10^3,2\leq x_i\leq 10^{18}.$

题目描述

Suppose you have a sequence of $ k $ integers $ A = [a_1, a_2, \dots , a_k] $ where each $ a_i \geq 2 $ . A sequence of prime integers $ P = [p_1, p_2, \dots, p_k] $ is called suitable for the sequence $ A $ if $ a_1 $ is divisible by $ p_1 $ , $ a_2 $ is divisible by $ p_2 $ and so on. A sequence of prime integers $ P $ is called friendly if there are no unique integers in this sequence. A sequence $ A $ is called ideal, if each sequence $ P $ that is suitable for $ A $ is friendly as well (i. e. there is no sequence $ P $ that is suitable for $ A $ , but not friendly). For example, the sequence $ [2, 4, 16] $ is ideal, while the sequence $ [2, 4, 6] $ is not ideal (there exists a sequence $ P = [2, 2, 3] $ which is suitable for $ A $ , but not friendly). You are given $ n $ different integers $ x_1 $ , $ x_2 $ , ..., $ x_n $ . You have to choose exactly $ k $ of them in such a way that they form an ideal sequence, or report that it is impossible. Note that no integer can be chosen more than once.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ k $ ( $ 1 \leq k \leq n \leq 1000 $ ). The second line contains $ n $ pairwise distinct integers $ x_1 $ , $ x_2 $ , ..., $ x_n $ ( $ 2 \leq x_i \leq 10^{18} $ ).

输出格式

If it is impossible to choose exactly $ k $ integers from $ x_1 $ , $ x_2 $ , ..., $ x_n $ in such a way that the chosen integers form an ideal sequence, print $ 0 $ . Otherwise, print $ k $ pairwise distinct integers — the elements of the chosen ideal sequence. If there are multiple answers, print any of them.

输入输出样例

输入样例 #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

题意翻译

对于一个包含 $k$ 个数字的序列 $A=[a_1,a_2,...a_k]$，若一个仅包含 $k$ 个质数的序列 $P=[p_1,p_2,...,p_k]$ 满足对于所有整数 $i(1\leq i\leq k)$ 有 $p_i$ 是 $a_i$ 的因数，那么我们称这个序列 $P$ 就是序列 $A$ 的“合适”序列。 进一步的，我们称一个序列 $A$ 是“理想”序列仅当这个序列的任意“合适”序列都没有元素只出现一次，比如说序列 $[2,4,8]$ 是“理想”序列，因为他唯一的“合适”序列 $[2,2,2]$ 没有任何元素只出现一次，序列 $[4,6,8]$ 就不是“理想”序列，它有两个“合适”序列 $[2,2,2],[2,3,2]$,其中第二个“合适”序列里有一个唯一的元素 $3$。 现在给定长度为 $n$ 的初始序列 $X=[x_1,x_2,...,x_n]$ 和参数 $k$，你要选出 $X$ 当中的 $k$ 个元素，并组成一个“理想”序列，如果有解，输出这个序列（输出任意一个合法解即可），无解输出一个 $0$。 $1\leq k\leq n\leq10^3,2\leq x_i\leq 10^{18}.$