题目简述

给定一个由 $n$ 个互不相同的正整数组成的数组 $a_1, a_2, \dots, a_n$。你可以选择一个正整数 $k$（$1 \le k \le 10^{18}$），然后将每个 $a_i$ 替换为 $a_i \bmod k$。要求操作后的数组中恰好包含两个不同的数值。题目保证这样的 $k$ 一定存在，你只需输出任意一个。

解题思路

设 $f(k)$ 表示使用模数 $k$ 操作后，数组 $a$ 中不同余数的个数。
我们尝试从 $k=2$ 开始，如果此时 $f(2)=2$，则直接输出 $2$。否则 $f(2)=1$，即所有数模 $2$ 的余数相同，也就是说所有 $a_i$ 要么全是偶数，要么全是奇数。

考虑一般情况：假设 $f(k)=1$，即所有 $a_i \bmod k$ 都等于同一个值 $x$。那么对于 $2k$，每个 $a_i$ 可以写为 $a_i = q_i \cdot k + x$。

• 如果 $q_i$ 是偶数，则 $a_i \bmod (2k) = x$；
• 如果 $q_i$ 是奇数，则 $a_i \bmod (2k) = x + k$。

因此，从 $k$ 翻倍到 $2k$ 时，余数最多分裂成两个值 $x$ 和 $x+k$。若所有 $q_i$ 同奇偶，则 $f(2k)=1$，否则 $f(2k)=2$。

由于 $a_i$ 互不相同且 $n \ge 2$，$f(k)$ 从 $k=1$ 时的 $1$ 开始，随着 $k$ 不断翻倍，最终一定会出现分裂（因为当 $k > \max a_i$ 时，$a_i \bmod k = a_i$，此时 $f(k)=n \ge 2$）。因此，存在某个 $m$ 使得 $f(2^m)=1$ 且 $f(2^{m+1})=2$。我们只需从 $k=2$ 开始不断翻倍，直到 $f(k)=2$ 为止。

算法步骤

1. 读入 $t$ 组数据。
2. 对每组数据：
   • 读入 $n$ 和数组 $a$。
   • 初始化 $k = 2$。
   • 循环：
     • 计算所有 $a_i \bmod k$ 并放入集合 $S$。
     • 如果 $|S| = 2$，输出 $k$ 并退出循环。
     • 否则 $k \leftarrow 2k$。

复杂度分析

• 每次检查 $|S|$ 需要 $O(n)$ 时间。
• $k$ 最多翻倍 $O(\log \max a_i)$ 次，因为当 $k > \max a_i$ 时必然有 $|S| = n$。
• 每组数据时间复杂度 $O(n \log \max a_i)$，完全满足 $n \le 100, \max a_i \le 10^{17}$ 的限制。

正确性证明

引理 1：若 $f(k)=1$，则 $f(2k) \in \{1,2\}$。
证明：如前所述，所有 $a_i \bmod k = x$，则 $a_i \bmod (2k)$ 只能是 $x$ 或 $x+k$，因此至多两种。

引理 2：存在 $m$ 使得 $f(2^m)=1$ 且 $f(2^{m+1})=2$。
证明：当 $m=0$ 时 $k=1$，$f(1)=1$。当 $m$ 足够大使得 $2^m > \max a_i$ 时，$a_i \bmod 2^m = a_i$，由于 $a_i$ 互不相同，$f(2^m)=n \ge 2$。因此从 $m=0$ 到 $m$ 足够大的过程中，$f(2^m)$ 从 $1$ 变为 $\ge 2$。由引理 1，每次翻倍 $f$ 要么不变要么从 $1$ 变成 $2$，所以必然存在某个 $m$ 使得 $f(2^m)=1$ 且 $f(2^{m+1})=2$。此时 $k=2^{m+1}$ 即为所求。

算法正确性：我们从 $k=2$ 开始，若 $f(2)=2$ 则直接输出；否则 $f(2)=1$，此时继续翻倍。根据上述论证，一定会在某个 $k=2^j$ 时出现 $f(k)=2$，因此算法总能找到合法解。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<long long> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        long long k = 2;
        while (true) {
            set<long long> s;
            for (long long x : a) {
                s.insert(x % k);
            }
            if (s.size() == 2) {
                cout << k << "\n";
                break;
            }
            k *= 2;
        }
    }
    return 0;
}

总结

本题的核心在于利用模数翻倍时余数的分裂性质，通过倍增法快速找到满足条件的 $k$。该方法简洁高效，且符合题目要求的数据范围。