CF2173C 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$，或者判断不存在这样的集合。

每组测试数据包含多组测试用例。第一行包含一个整数 $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$。

对于每组测试用例： - 如果不存在完备集合 $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=\{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$ 中出现了。 由 ChatGPT 5 翻译