← 返回题目列表

Codeforces · 2021/B

B. 最大化墨西哥

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

给定一个由 $$$n$$$ 正整数组成的数组 $$$a$$$ 和一个整数 $$$x$$$。您可以执行以下两步操作任意次(可能为零):

1. 选择索引 $$$i$$$ ($$$1 \leq i \leq n$$$)。
2. 将 $$$a_i$$$ 增加 $$$x$$$,换句话说 $$$a_i := a_i + x$$$。

如果您以最佳方式执行运算,请找到 $$$\operatorname{MEX}$$$ 的 $$$a$$$ 的最大值。

数组的 $$$\operatorname{MEX}$$$(最小排除值)是不在数组中的最小非负整数。例如:

- $$$[2,2,1]$$$ 的 $$$\operatorname{MEX}$$$ 是 $$$0$$$,因为 $$$0$$$ 不在数组中。
- $$$[3,1,0,1]$$$ 的 $$$\operatorname{MEX}$$$ 是 $$$2$$$,因为 $$$0$$$ 和 $$$1$$$ 在数组中,但 $$$2$$$ 不在数组中。
- $$$[0,3,1,2]$$$ 的 $$$\operatorname{MEX}$$$ 是 $$$4$$$,因为 $$$0$$$、$$$1$$$、$$$2$$$ 和 $$$3$$$ 在数组中,但 $$$4$$$ 不在数组中。

输入

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

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$x$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le x \le 10^9$$$) - 数组的长度和运算中要使用的整数。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) - 给定的数组。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数:如果以最佳方式执行操作,则 $$$a$$$ 的最大 $$$\operatorname{MEX}$$$ 。

示例

输入 #1

3
6 3
0 3 2 1 5 2
6 2
1 3 4 1 0 2
4 5
2 5 10 3

输出 #1

4
6
0

注意

在第一个测试用例中,$$$a$$$ 的 $$$\operatorname{MEX}$$$ 在不执行任何操作的情况下为 $$$4$$$,这是最大值。

在第二个测试用例中,$$$a$$$ 的 $$$\operatorname{MEX}$$$ 为 $$$5$$$,未执行任何操作。如果我们使用 $$$i=1$$$ 执行两个操作,我们将得到数组 $$$a=[5,3,4,1,0,2]$$$。那么$$$a$$$的$$$\operatorname{MEX}$$$将变成$$$6$$$,这是最大值。

在第三个测试用例中,$$$a$$$的$$$\operatorname{MEX}$$$在不执行任何操作的情况下为$$$0$$$,这是最大值。