P16392 [IATI 2024] Lex_gcd

你的任务是，给定一个包含 $N$ 个正整数的序列 $a_1, a_2, \ldots, a_N$，在允许的预处理之后，找出它字典序最小的 $K$-$\gcd$ 等价**排列**。若两个序列互为排列，且对于任意一组从 $1$ 到 $N$ 中选出的 $K$ 个互异下标，两序列在这些位置上的元素的最大公约数（$\gcd$）都相同，则称这两个序列是 $K$-$\gcd$ 等价的。 不过有一个附加条件 —— 在寻找这个字典序最小的 $K$-$\gcd$ 等价序列之前，你最多可以将 $a$ 中的一个元素乘以给定的整数 $X$。你也可以完全不乘 $X$ 而保持原序列不变。此外，题目保证 $X$ 仅能被 $1$ 和自身整除。你的目标是在所有可能的预处理选择（包括不做预处理）中，使得最终得到的序列字典序最小。 请编写一个程序 $\texttt{lex\_gcd}$ 来解决该问题。

第一行包含一个整数 $T$，表示测试数据的组数。每组测试数据包含三个正整数 $N$, $K$ 和 $X$，之后跟着 $N$ 个正整数 $a_1, a_2, \ldots, a_N$。

对于每组测试数据，输出 $N$ 个整数，表示在完成允许的预处理后，字典序最小的 $K$-$\gcd$ 等价排列。

### 样例解释 共有两组测试数据。对于第一组，无需预处理。序列的 $K$-$\gcd$ 性质已满足，因为所有数对的最大公约数均为 $2$。对于第二组，将第一个元素乘以 $3$ 进行预处理后，得到字典序最小的序列 $3, 6, 9, 21$。 ### 数据范围 - 所有测试数据中 $N$ 的总和不超过 $10^5$； - $2 \leq K \leq N$； - $1 \leq X \leq 10^9$，且 $X$ 要么为 $1$ 要么为质数； - $1 \leq a_i \leq 10^9$。 ### 子任务 | **子任务** | **分值** | **依赖子任务** | **$N$** | **$X$** | **其他限制** | | :---: | :---: | :---: | :---: | :---: | :---: | | $1$ | $6$ | $-$ | $\sum N \leq 5$ | $X = 1$ | $-$ | | $2$ | $19$ | $1$ | $\sum N \leq 1000$ | $X = 1$ | $-$ | | $3$ | $13$ | $1-2$ | $\sum N \leq 10^5$ | $X = 1$ | $-$ | | $4$ | $4$ | $1$ | $\sum N \leq 100$ | $-$ | $-$ | | $5$ | $4$ | $1,2,4$ | $\sum N \leq 1000$ | $-$ | $-$ | | $6$ | $31$ | $-$ | $\sum N \leq 10^5$ | $-$ | 对于 $i \neq j$ 有 $a_i \neq a_j$ | | $7$ | $23$ | $1-6$ | $\sum N \leq 10^5$ | $-$ | $-$ | 只有在成功通过某子任务的所有测试及其所需依赖子任务的所有测试后，才能获得该子任务的分数。 翻译由 DeepSeek V4 Pro 完成