Moe's CF Life

喵~ 主人，你好呀！Mimi 今天又来给你讲解有趣的算法题啦！这次的题目是 Codeforces 上的 B. Make Almost Equal With Mod，一个关于取模的小谜题，但是很有趣哦，嘿嘿。

题目大意 (Problem Description)

主人，听好了喵！题目是这样子的：

我们有一个包含 n 个不同的正整数的数组 a。我们需要做一次操作：

选择一个正整数 k ( 1 ≤ k ≤ 10^18 )。
将数组 a 中的每一个元素 a_i 都替换成 a_i mod k (也就是 a_i 除以 k 的余数)。

我们的目标是，找到一个合适的 k，使得操作结束后的新数组里，恰好只有两种不同 的数值。

题目保证了，在给定的条件下，这样的 k 一定存在。如果有很多个 k 都能满足条件，我们随便输出一个就可以啦，喵~

举个例子，如果数组是 [8, 15, 22, 30]，我们可以选 k=7。

8 mod 7 = 1
15 mod 7 = 1
22 mod 7 = 1
30 mod 7 = 2 新的数组就变成了 [1, 1, 1, 2]，里面只有 1 和 2 两种不同的值，完全符合要求，喵！

解题思路 (Solution Approach)

刚看到这道题的时候，Mimi 的小脑袋也转了好几圈呢。k 的范围那么大，从 1 到 10^18，我们肯定不能一个一个去试呀，那要试到什么时候去嘛！(｡•́︿•̀｡)

所以，我们需要找到一种更聪明的方法来构造这个 k。

题目的关键是让所有 a_i mod k 的结果只有两种。这意味着，我们选择的 k 要能把原始数组 a 里的所有数字分成两拨。

我们来想想数字最基本的分组方式是什么？当然是奇数和偶数啦！喵~

根据奇偶性分组
我们可以把数组 a 里的数字分成两组：奇数集合和偶数集合。
- 如果我们选择 k=2，那么所有的奇数 a_i 都会变成 a_i mod 2 = 1，所有的偶数 a_i 都会变成 a_i mod 2 = 0。
- 如果原始数组里既有奇数又有偶数，那 k=2 不就正好能让结果集变成 {0, 1} 这两种值吗？这不就是一个完美的答案了嘛！
如果所有数奇偶性相同怎么办？
那如果数组里所有的数都是奇数，或者所有的数都是偶数呢？
- 这时候用 k=2 的话，所有 a_i mod 2 的结果就都一样了（要么全是 1，要么全是 0），只剩下一种值，不满足题目要求。
这时候我们就要想个新办法了。既然 k=2 不行，我们能不能试试 k=4, k=8, k=16 ... 也就是 k = 2^p 这样的数呢？
这个想法真是太棒了，让 Mimi 来给你解释一下为什么它一定能行，喵！
我们来观察一下数字的二进制表示。
- a_i mod 2 其实就是看 a_i 的二进制的最后一位 (第0位)。如果所有数的奇偶性相同，说明它们二进制的最后一位都相同。
- a_i mod 4 就是看 a_i 的二进制的最后两位 (第1位和第0位)。
- a_i mod 8 就是看 a_i 的二进制的最后三位 (第2, 1, 0位)。
- ...
- a_i mod 2^p 就是看 a_i 的二进制的最后 p 位。
因为题目保证了数组里所有的 a_i 都是不同的，所以它们的二进制表示肯定不会完全一样。这意味着，只要我们把 p 变得足够大，a_i mod 2^p 的结果最终肯定会变得各不相同。
所以，我们可以这样做：
- 从 p=1 开始，尝试 k = 2^1 = 2。
- 计算所有 a_i mod k，看看有几种不同的余数。
- 如果是 2 种，太棒了，我们找到了答案！
- 如果是 1 种，说明 k 还不够大，我们继续试下一个，p=2，也就是 k = 2^2 = 4。
- ...
- 我们不断地增加 p，尝试 k = 2^p。
最神奇的地方来啦！Mimi 发现，当我们这样不断增大 p 的时候，不同余数的数量是不会从 1 直接跳到 3 或更多的！也就是说，只要我们找到第一个能让余数种类超过 1 的 k = 2^p，那余数的种类必定是 2！
为什么呢？(一个简单的证明喵)
假设对于 k' = 2^(p-1)，所有 a_i mod k' 的结果都相同，等于某个值 r。这意味着，所有的 a_i 都可以写成 a_i = q_i * 2^(p-1) + r 的形式。
现在我们来看 k = 2^p = 2 * 2^(p-1)。 a_i mod k 的值是多少呢？这取决于 q_i 的奇偶性。
- 如果 q_i 是偶数，q_i = 2m，那么 a_i = 2m * 2^(p-1) + r = m * 2^p + r。所以 a_i mod k = r。
- 如果 q_i 是奇数，q_i = 2m+1，那么 a_i = (2m+1) * 2^(p-1) + r = m * 2^p + 2^(p-1) + r。所以 a_i mod k = r + 2^(p-1)。
看吧！a_i mod k 的结果只可能有两种：r 和 r + 2^(p-1)。因为我们是从 p=1 开始，找到的第一个让余数种类不止一种的 p，所以数组中肯定既有 q_i 是偶数的情况，也有 q_i 是奇数的情况。因此，余数种类就正好是 2 种啦！
所以我们的最终策略就是：依次尝试 k = 2, 4, 8, 16, ...，直到找到一个 k 使得 a_i mod k 的结果恰好有两种。 题目保证有解，所以这个方法一定能找到答案，喵~

题解代码 (Solution Code)

这是 Mimi 写的 C++ 代码，主人可以参考一下哦！

cpp

#include <iostream>
#include <vector>
#include <set>

void solve() {
    int n;
    std::cin >> n;
    std::vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // 我们来尝试 k = 2^p, p 从 1 开始
    // 题目保证一定有解，所以这个循环肯定能找到答案
    for (int p = 1; p < 63; ++p) {
        // k = 2^p，用位运算来写，又快又方便，喵~
        // 1LL 保证了我们在进行 64 位整数的运算
        long long k = 1LL << p;
        
        // 用一个 set 来存储所有不同的余数
        // set 会自动处理重复的元素，purrfect!
        std::set<long long> distinct_remainders;
        for (long long val : a) {
            distinct_remainders.insert(val % k);
        }

        // 如果 set 的大小是 2，说明我们找到了！
        if (distinct_remainders.size() == 2) {
            std::cout << k << std::endl;
            return; // 找到答案就结束这个测试用例啦
        }
    }
}

int main() {
    // 加速输入输出，让程序跑得像小猫一样快~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

题目大意 (Problem Description) ​

解题思路 (Solution Approach) ​

题解代码 (Solution Code) ​

相关知识点 (Knowledge Points) ​

题目大意 (Problem Description)

解题思路 (Solution Approach)

题解代码 (Solution Code)

相关知识点 (Knowledge Points)