CF1176D Recover it!

作者猜测了一个由 $n$ 个整数构成的数组 $a$，其中每个整数都不小于 $2$ 且不大于 $2 \cdot 10^5$。你并不知道数组 $a$，但你知道通过以下操作得到的数组 $b$： 1. 首先，让数组 $b$ 等于数组 $a$； 2. 然后，对于每个 $i$ 从 $1$ 到 $n$： - 如果 $a_i$ 是质数，则将一个整数 $p_{a_i}$ 添加到数组 $b$，其中 $p$ 是质数的无限序列（$2, 3, 5, \dots$）； - 否则（如果 $a_i$ 不是质数），将 $a_i$ 的最大真因子（不等于 $a_i$ 的最大因子）添加到 $b$； 3. 最后，将得到的长度为 $2n$ 的数组随机打乱顺序，并作为输入给你。 这里 $p_{a_i}$ 表示第 $a_i$ 个质数。第一个质数 $p_1 = 2$，第二个质数是 $p_2 = 3$，以此类推。 你的任务是还原出任意一个可以生成给定数组 $b$ 的数组 $a$。保证一定存在解（即数组 $b$ 是由某个合法的数组 $a$ 生成的）。如果有多组解，你可以输出任意一组。

第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示数组 $a$ 的元素个数。 第二行包含 $2n$ 个整数 $b_1, b_2, \dots, b_{2n}$（$2 \le b_i \le 2750131$），其中 $b_i$ 是数组 $b$ 的第 $i$ 个元素。$2750131$ 是第 $199999$ 个质数。

输出一行 $n$ 个整数 $a_1, a_2, \dots, a_n$（$2 \le a_i \le 2 \cdot 10^5$），表示可以生成给定数组 $b$ 的数组 $a$，顺序任意。如果有多组解，你可以输出任意一组。

由 ChatGPT 4.1 翻译