← 返回题目列表

Codeforces · 2134/B

B. 添加 0 或 K

中文机器翻译题面 查看原题

给定一个由 $$$n$$$ 正整数 $$$a_1、a_2、\ldots、a_n$$$ 和一个正整数 $$$k$$$ 组成的数组。

在一次操作中,您可以将 $$$0$$$ 或 $$$k$$$ 添加到每个 $$$a_i$$$,即,选择另一个 $$$n$$$ 整数 $$$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) \gt 1$$$ $$$^{\text{*}}$$$。可以证明,这总是可能的。

输出运算后的最终数组。你做的 不 必须输出操作本身。

$$$^{\text{*}}$$$$$$\gcd(a_1, a_2, \ldots, a_n)$$$ 表示 $$$a_1, a_2, \ldots, a_n$$$ 的最大公约数 (GCD)。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 10^5$$$, $$$1 \leq k \leq 10^9$$$) - 数组 $$$a$$$ 的长度和给定常量。

每个测试用例的第二行包含 $$$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
3 3
2 7 1
4 5
2 9 16 14
4 1
1 2 3 4
5 2
5 6 7 8 9
2 10
7 9
1 1000000000
1
1 371
1000000000
3 6
1 3 5

输出
复制

8 10 10
7 14 21 14
2 2 4 4
9 6 9 12 9
77 99
1000000000000000001
1000000000
25 15 5

注意

在第一个测试用例中,输出 $$$[8,10,10]$$$ 有效,因为 $$$\gcd(8, 10, 10) = 2 \gt 1$$$,并且数组 $$$[2, 7, 1]$$$ 最多可以使用 $$$3$$$ 操作转换为 $$$[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 \gt 1$$$。
  • 从 $$$[2, 9, 16, 14]$$$ 开始,应用 $$$b = [5, 5, 5, 0]$$$ 的运算得到 $$$[7, 14, 21, 14]$$$,需要不超过 $$$5$$$ 运算。