C. Blackslex and Number Theory

时间限制：每测试点 2 秒
内存限制：每测试点 256 兆字节

问题描述

Blackslex 工作太努力，开始梦到数字。请解决他梦中的以下任务。

给定一个数组 $a_1, a_2, \dots, a_n$。

在一次操作中，你选择一个索引 $i$ $(1 \le i \le n)$ 和一个不小于 $k$ 的整数 $x$，并执行赋值： $$ a_i := a_i \bmod x, $$ 其中 $u \bmod v$ 表示 $u$ 除以 $v$ 的余数。

你的目标是使数组的所有元素相同。在所有正整数 $k$ 中，确定最大的 $k$，使得存在一系列上述操作（操作次数有限），使得所有数组元素相等。

输入格式

第一行包含一个整数 $t$ $(1 \le t \le 10^4)$ —— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ $(2 \le n \le 2 \cdot 10^5)$。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ $(1 \le a_i \le 10^9)$，所有 $a_i$ 的值互不相同。

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

输出格式

对于每个测试用例，输出一个整数 —— 最大的正整数 $k$，使得可以使用模数 $x$ 被限制为 $k \le x$ 的任意次操作，使得数组的所有元素相等。

样例输入

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

样例输出

5
2
6

AC 代码

// Problem: CF 2179 C
// Contest: Codeforces - Codeforces Round 1071 (Div. 3)
// URL: https://codeforces.com/contest/2179/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false);cin.tie(nullptr);
#define int long long


int check(int x,vector<int>& a){
    int cnt=0;
    for(int i=0;i<a.size();i++){
        if(a[i]<x) cnt++;
        if(cnt>=2) break;
    }
    if(cnt==2) return 0;
    else if(cnt==1){
        int p=a[0];
        for(int i=1;i<a.size();i++){
            if(a[i]<2*x){
                if(a[i]%x<p) return 0;
            } 
        }
        return 1;
    }else return 1;
}

void solve(){
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a.begin(),a.end());
    int l=0,r=1e9;
    while(l<r){
        int mid=(l+r+1)/2;
        if(check(mid,a)) l=mid;
        else r=mid-1;
    }
    cout<<l<<endl;
    return ;
}

signed main(){
    ios;
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

写完这个题目，我觉得我对取模有了新的理解（其实相当于一直减那个模的数字，你可能觉得我在说废话，可能吧）

这段代码写得非常精简且正确！如果你觉得之前的解释太绕了，那我们把那些“动态 x”、“同余”的术语全部扔掉。

我们只看这段代码在干什么，以及为什么这么做是对的。

这段代码的核心逻辑

这段代码其实只做了一件事：

比较 a[0] 和 a[1] - a[0] 谁更大，输出大的那个。

代码里的 if (a[1] > a[0] * 2) 其实就是个数学变形：

• 移项前：a[1] > a[0] * 2

• 移项后：a[1] - a[0] > a[0]

也就是问：第二个数和最小值的差，是不是比最小值本身还大？

---

为什么只需要看这两个数？

要把所有数字变成一样，其实只有两条路可选。我们就像“砍木头”一样来理解：

第一条路：把大家都砍成 0

• 目标：所有数模运算后变成 0。

• 瓶颈：你手里最小的木头是 a[0]。

  • 对于 a[0]，要让它变成 0，模数 $k$ 最大只能取 a[0]（因为 $a[0] \% a[0] = 0$）。

  • 对于比 a[0] 大的数，比如 a[1]，我们总能找到办法（比如直接取 $k=a[1]$）。

• 结论：走这条路，答案上限是 a[0]。

第二条路：把大家都砍成 a[0]

• 目标：所有数模运算后变成 a[0]。

• 瓶颈：看看 a[1]（第二小的数）。

  • a[1] 必须变成 a[0]。也就是要把 a[1] 多出来的部分 a[1] - a[0] 切掉。

  • 模运算的性质决定了，我们选的模数 $k$ 必须能整除这个“多出来的部分”。

  • 所以，$k$ 最大只能取 a[1] - a[0]。

  • 至于更大的数 a[2], a[3]...，它们多出来的部分肯定比 a[1] 多，更容易满足条件，所以瓶颈只在 a[1]。

• 结论：走这条路，答案上限是 a[1] - a[0]。

---

举两个例子秒懂

例子 1：输入 5 7 9

• 排序后：a[0]=5, a[1]=7。

• 路 1 (全变0)：最大能用的 $k$ 是 5。

• 路 2 (全变5)：a[1] 要变 5，多出来的部分是 $7-5=2$。最大能用的 $k$ 是 2。

• 选哪条？ 5 比 2 大，选 5。

• 代码逻辑：a[1] (7) 不大于 a[0]*2 (10)，走 else，输出 a[0] (5)。正确。

例子 2：输入 2 9

• 排序后：a[0]=2, a[1]=9。

• 路 1 (全变0)：最大能用的 $k$ 是 2。

• 路 2 (全变2)：a[1] 要变 2，多出来的部分是 $9-2=7$。最大能用的 $k$ 是 7。

• 选哪条？ 7 比 2 大，选 7。

• 代码逻辑：a[1] (9) 大于 a[0]*2 (4)，走 if，输出 a[1]-a[0] (7)。正确。

总结

你不需要管每个数具体除以几。你只需要在这个数组里做一次选择：

1. 是保留最小值 a[0] 当答案？

2. 还是把最小值和第二小值的差 a[1]-a[0] 当答案？

谁大选谁。 这就是这道题的全部真理。你的代码完全没问题。