A16536. Kanade's Perfect Multiples
编程题
普及-
知识点
题目描述
我们已经把那些回忆刻在了心里……无论它们有多么辛苦，那都是我们所经历过的人生！
——Angel Beats！
在死后世界学园中，奏在研究一种奇特的数字游戏。
她给你两个整数 $n$ 和 $k$，以及一个由 $n$ 个整数组成的数组 $a$，其中 $1 \le a_i \le k$ 恒成立。
对于一个整数集合 $B = \{b_1, b_2, \ldots, b_m\}$，其中 $1 \le b_i \le k$，当且仅当同时满足下列两个条件时，我们称它为完备集合：
- 对于每个 $1\le i\le n$，$a_i$ 的至少一个因数在 $B$ 中；
- 对于每个 $1\le j\le m$，所有 $b_j$ 的正整数倍且小于等于 $k$ 的数，至少在数组 $a$ 中出现过一次。
你需要找到一个大小最小的完备集合 $B$，或者判断不存在这样的集合。
——Angel Beats！
在死后世界学园中，奏在研究一种奇特的数字游戏。
她给你两个整数 $n$ 和 $k$，以及一个由 $n$ 个整数组成的数组 $a$，其中 $1 \le a_i \le k$ 恒成立。
对于一个整数集合 $B = \{b_1, b_2, \ldots, b_m\}$，其中 $1 \le b_i \le k$，当且仅当同时满足下列两个条件时，我们称它为完备集合：
- 对于每个 $1\le i\le n$，$a_i$ 的至少一个因数在 $B$ 中；
- 对于每个 $1\le j\le m$，所有 $b_j$ 的正整数倍且小于等于 $k$ 的数，至少在数组 $a$ 中出现过一次。
你需要找到一个大小最小的完备集合 $B$，或者判断不存在这样的集合。
输入格式
每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。
每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1\le n\le 2\cdot 10^5$，$1\le k\le 10^9$）——数组 $a$ 的长度及其元素的上界。
第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1\le a_i\le k$）——数组 $a$ 的各个元素。
保证所有测试用例中 $n$ 的总和不超过 $2\cdot10^5$。
每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1\le n\le 2\cdot 10^5$，$1\le k\le 10^9$）——数组 $a$ 的长度及其元素的上界。
第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1\le a_i\le k$）——数组 $a$ 的各个元素。
保证所有测试用例中 $n$ 的总和不超过 $2\cdot10^5$。
输出格式
对于每组测试用例：
- 如果不存在完备集合 $B$，只需在一行中输出一个整数 $-1$。
- 否则：
- 首先输出一行一个整数 $m$（$1\le m\le n$），表示 $B$ 的大小，且要求使 $m$ 最小。
- 第二行输出 $m$ 个整数 $b_1,b_2,\ldots,b_m$（$1\le b_i\le k$），表示你构造的集合 $B$。
如果存在多种答案，输出任意一种均可。
- 如果不存在完备集合 $B$，只需在一行中输出一个整数 $-1$。
- 否则：
- 首先输出一行一个整数 $m$（$1\le m\le n$），表示 $B$ 的大小，且要求使 $m$ 最小。
- 第二行输出 $m$ 个整数 $b_1,b_2,\ldots,b_m$（$1\le b_i\le k$），表示你构造的集合 $B$。
如果存在多种答案，输出任意一种均可。
输入输出样例
输入 #1
4 4 6 3 2 4 6 5 5 1 2 3 4 5 3 6 2 3 6 1 2 2
输出 #1
2 2 3 1 1 -1 1 2
说明/提示
在第一个测试用例中，$B=\{2,3\}$ 符合要求。对于 $b=2$，所有倍数 $\{2,4,6\}$（不超过 $k=6$）都在 $a$ 中出现过；对于 $b=3$，所有倍数 $\{3,6\}$ 也都出现了。每个 $a_i$ 都能被 $2$ 或 $3$ 整除。没有单个 $b$ 能同时满足这两个条件，所以 $m=2$ 是最小的。
在第二个测试用例中，$B=\{1\}$ 满足条件，因为每个数都能被 $1$ 整除，且 $1$ 的所有倍数（即 $1,2,3,4,5$，不超过 $k$）都在 $a$ 中出现了。
在第二个测试用例中，$B=\{1\}$ 满足条件，因为每个数都能被 $1$ 整除，且 $1$ 的所有倍数（即 $1,2,3,4,5$，不超过 $k$）都在 $a$ 中出现了。