← 返回题目列表

Codeforces · 1909/B

B. 与 Mod 几乎相等

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

给定一个由不同正整数组成的数组 $$$a_1, a_2, \dots, a_n$$$。您必须执行以下操作一次:

- 选择一个正整数$$$k$$$;
- 对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$,将 $$$a_i$$$ 替换为 $$$a_i \text{ mod } k^\dagger$$$。

找到 $$$k$$$ 的值,使得 $$$1 \leq k \leq 10^{18}$$$ 并且数组 $$$a_1, a_2, \dots, a_n$$$ 在操作结束时恰好包含 $$$2$$$ 不同的值。可以证明,在问题的约束下,至少存在一个这样的$$$k$$$。如果有多个解决方案,您可以打印其中任何一个。

$$$^\dagger$$$ $$$a \text{ mod } b$$$ 表示 $$$a$$$ 除以 $$$b$$$ 后的余数。例如:

- $$$7 \text{ mod } 3=1$$$ 因为 $$$7 = 3 \cdot 2 + 1$$$
- $$$15 \text{ mod } 4=3$$$ 因为 $$$15 = 4 \cdot 3 + 3$$$
- $$$21 \text{ mod } 1=0$$$ 因为 $$$21 = 21 \cdot 1 + 0$$$

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 100$$$) — 数组 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^{17}$$$) — 数组的初始状态。保证所有 $$$a_i$$$ 都是不同的。

请注意,所有测试用例的 $$$n$$$ 总和没有限制。

输出

对于每个测试用例,输出一个整数:值 $$$k$$$ ($$$1 \leq k \leq 10^{18}$$$) 使得数组 $$$a_1, a_2, \dots, a_n$$$ 在操作结束时恰好包含 $$$2$$$ 不同值。

示例

输入 #1

5
4
8 15 22 30
5
60 90 98 120 308
6
328 769 541 986 215 734
5
1000 2000 7000 11000 16000
2
2 1

输出 #1

7
30
3
5000
1000000000000000000

注意

在第一个测试用例中,您可以选择 $$$k = 7$$$。该数组变为 $$$[8 \text{ mod } 7, 15 \text{ mod } 7, 22 \text{ mod } 7, 30 \text{ mod } 7] = [1, 1, 1, 2]$$$,其中恰好包含 $$$2$$$ 不同值 ($$$\{1, 2\}$$$)。

在第二个测试用例中,您可以选择 $$$k = 30$$$。该数组变为 $$$[0, 0, 8, 0, 8]$$$,其中恰好包含 $$$2$$$ 不同值 ($$$\{0, 8\}$$$)。请注意,选择 $$$k = 10$$$ 也是一个有效的解决方案。

在最后一个测试用例中,您可以选择 $$$k = 10^{18}$$$。该数组变为 $$$[2, 1]$$$,其中恰好包含 $$$2$$$ 不同值 ($$$\{1, 2\}$$$)。请注意,选择 $$$k = 10^{18} + 1$$$ 无效,因为 $$$1 \leq k \leq 10^{18}$$$ 必须为真。