CF2134B Add 0 or K

给定一个包含 $n$ 个正整数的数组 $a_1, a_2, \ldots, a_n$ 和一个正整数 $k$。 在一次操作中，你可以对每个 $a_i$ 加上 $0$ 或 $k$，即选择另一个数组 $b_1, b_2, \ldots, b_n$，其中每个 $b_i$ 要么是 $0$，要么是 $k$，然后将 $a_i$ 更新为 $a_i + b_i$，对于所有 $1 \le i \le n$。注意，对于数组 $b$ 的每一个元素，你可以选择不同的值。 你的任务是在不超过 $k$ 次操作内，使得 $\gcd(a_1, a_2, \ldots, a_n) > 1$ $^{\text{∗}}$。可以证明，永远存在合法解。 请输出经过操作后的最终数组。你不需要输出具体的操作过程。 $^{\text{∗}}$ $\gcd(a_1, a_2, \ldots, a_n)$ 表示 $a_1, a_2, \ldots, a_n$ 的最大公约数（greatest common divisor, GCD）。

本题包含多组测试数据。第一行为测试组数 $t$（$1 \le t \le 1000$）。每组测试数据描述如下。 每组测试数据的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 10^5$，$1 \leq k \leq 10^9$），分别表示数组长度和给定常数。 第二行为 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1 \le a_i \le 10^9$），表示数组 $a$ 的各个元素。 保证所有测试数据中 $n$ 之和不超过 $10^5$。

对于每组测试数据，输出一行 $n$ 个整数，表示经过操作后的最终数组。输出的各元素要求都在 $1$ 到 $10^9 + k^2$ 之间。 如果有多种合法输出，只需输出其中一种即可。 注意，你无需最小化操作次数。

在第一个测试用例中，输出 $[8, 10, 10]$ 是合法的，因为 $\gcd(8, 10, 10) = 2 > 1$，并且可以通过不超过 $3$ 次操作将 $[2, 7, 1]$ 变为 $[8, 10, 10]$。一种可能的操作如下表： |操作次数|$b$ |操作后的 $a$| |:-------:|:-------:|:--------:| |$1$ |$[3, 0, 3]$|$[5, 7, 4]$ | |$2$ |$[0, 0, 3]$|$[5, 7, 7]$ | |$3$ |$[3, 3, 3]$|$[8, 10, 10]$| 其他诸如 $[2, 10, 4]$、$[8, 16, 4]$、$[5, 10, 10]$ 也是合法输出。 在第二个测试用例中，输出 $[7, 14, 21, 14]$ 是合法的，因为： - $\gcd(7, 14, 21, 14) = 7 > 1$。 - 从 $[2, 9, 16, 14]$ 出发，选择 $b = [5, 5, 5, 0]$，即可到达 $[7, 14, 21, 14]$，且操作次数不超过 $5$ 次。 由 ChatGPT 5 翻译