当前没有测试数据。

C. Blackslex and Number Theory

题目描述

Blackslex 工作太努力了，开始梦见数字。请解决他梦中的这个问题。

给定一个数组 a_1, a_2, ..., a_n。

在一次操作中，你可以选择一个索引 i（1 ≤ i ≤ n）和一个至少为 k 的整数 x，并执行以下操作： a_i = a_i mod x 其中 u mod v 表示 u 除以 v 的余数（即取余运算，结果在 0 到 v-1 之间）。

你的目标是让数组的所有元素变得相同。在所有正整数 k 中，找出最大的 k，使得存在有限次上述操作（其中模数 x 满足 k ≤ x）能让所有数组元素变得相同。

输入格式

第一行包含一个整数 t（1 ≤ t ≤ 1e4）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 n（2 ≤ n ≤ 2e5）。

第二行包含 n 个整数 a_1, a_2, ..., a_n（1 ≤ a_i ≤ 1e9，所有 a_i 的值互不相同）。

保证所有测试用例的 n 之和不超过 2e5。

输出格式

对于每个测试用例，输出一个整数 —— 满足条件的最大正整数 k（即使用模数 x ≥ k 的操作能让所有元素相同的最大 k）。

样例输入

3
3
5 7 9
2
2 3
7
11 74 5 22 52 97 82

样例输出

5
2
6

样例解释

样例 1 解释

输入数组为 [5, 7, 9]，输出 k=5。

关键分析：

要让所有元素通过 x ≥ 5 的取余操作变得相同，核心思路是找到一个目标值 m，使得每个元素都能通过若干次 x ≥ 5 的取余得到 m。

可行方案（目标值 m=0）：

• 对于 5：选择 x=5（5 ≥ 5），执行 5 mod 5 = 0；
• 对于 7：选择 x=7（7 ≥ 5），执行 7 mod 7 = 0；
• 对于 9：选择 x=9（9 ≥ 5），执行 9 mod 9 = 0。

所有元素最终变为 0，满足条件。

为什么 k=6 不可行？

若 k=6，则 x 必须满足 x ≥ 6：

• 对于 5：任何 x ≥ 6 的取余结果都是 5（因为 5 < x，取余结果为自身）；
• 对于 7：x ≥ 6 时，取余结果只能是 0（x=7）、1（x=6）或 7（x>7），无法得到 5；
• 因此无法让所有元素相同，故 k=6 不可行。

综上，最大可行 k 为 5。

样例 2 解释

输入数组为 [2, 3]，输出 k=2。

关键分析：

目标是找到最大 k，使得通过 x ≥ k 的取余操作让 2 和 3 相同。

可行方案（目标值 m=0）：

• 对于 2：选择 x=2（2 ≥ 2），执行 2 mod 2 = 0；
• 对于 3：选择 x=3（3 ≥ 2），执行 3 mod 3 = 0。

所有元素最终变为 0，满足条件。

为什么 k=3 不可行？

若 k=3，则 x 必须满足 x ≥ 3：

• 对于 2：任何 x ≥ 3 的取余结果都是 2（因为 2 < x）；
• 对于 3：x ≥ 3 时，取余结果只能是 0（x=3）或 3（x>3），无法得到 2；
• 因此无法让所有元素相同，故 k=3 不可行。

综上，最大可行 k 为 2。

样例 3 解释

输入数组为 [11, 74, 5, 22, 52, 97, 82]，输出 k=6。

关键分析：

核心思路是找到目标值 m=5，所有元素可通过 x ≥ 6 的取余操作得到 5：

• 11：选择 x=6（6 ≥ 6），11 mod 6 = 5；
• 74：选择 x=69（69 ≥ 6），74 mod 69 = 5；
• 5：选择 x=7（7 ≥ 6），5 mod 7 = 5（因 5 < 7，取余结果为自身）；
• 22：选择 x=17（17 ≥ 6），22 mod 17 = 5；
• 52：选择 x=47（47 ≥ 6），52 mod 47 = 5；
• 97：选择 x=92（92 ≥ 6），97 mod 92 = 5；
• 82：选择 x=77（77 ≥ 6），82 mod 77 = 5。

所有元素最终变为 5，满足条件。

为什么 k=7 不可行？

若 k=7，则 x 必须满足 x ≥ 7：

• 对于 5：任何 x ≥ 7 的取余结果都是 5（因 5 < 7）；
• 对于 11：要得到 5 需满足 11 mod x = 5，即 x 是 11-5=6 的约数且 x>5，唯一可能的 x=6，但 6 < 7，不满足 x ≥ 7；
• 因此无法让所有元素相同，故 k=7 不可行。

综上，最大可行 k 为 6。