题解：2024牛客暑期多校第4场——H [Yet Another Origami Problem]

英文题干

Fried-chicken hates origami problems! He always fails at solving origami problems that others can solve easily (for example, CF1966E and HDU6822). However, today Fried-chicken is the problem setter! It's his turn to give contestants a very difficult origami problem!

Given an array a of length n, you can perform the following operations any number of times (possibly zero):

Choose an index p, and then perform one of the following two operations:

For all i such that $a_i ≤ a_p$ , let $a_i ← a_i 2(a_p - a_i)$ .
For all i such that $a_i ≥ a_p$ , let $a_i ← a_i - 2(a_i - a_p)$ .

For example, if the original array is [2, 4, 5, 3] and you choose p = 2 and perform operation 1, the array will become [6, 4, 5, 5]]

Now, you want to minimize the range of the array through these operations. Recall that the range of an array is the difference between the maximum and minimum elements of the array.

Input:

Each test contains multiple test cases. The first line contains the number of test cases $t(1\leq t\leq 10^5)$ . The description of the test cases follows.

The first line of each test case contains an integer $n(1\leq n\leq 10^5)$ , representing the length of the array.

The second line contains $n$ integers $a_1,a_2,...,a_n,(0\leq a_i\leq 10^{16})$ , describing the elements of the array $a$ in the initial state.

It is guaranteed that the sum of n over all test cases does not exceed $5\times 10^5$ .

Output:

For each test case, output one integer on a single line, representing the minimum range of the array after any number of operations.

中文题干

Fried-chicken讨厌折纸问题！他总是无法解决别人可以轻松解决的折纸问题（例如，CF1966E和HDU6822）。然而，今天Fried-chicken是问题解决者！轮到他给参赛者一个非常困难的折纸问题了！

给定一个长度为 n 的数组 a，您可以执行任意次数（可能为零）的以下操作：选择索引 p，然后执行以下两项操作之一：

对于所有 i 使得 $a_i ≤ a_p$ ，让 $a_i ← a_i 2(a_p - a_i)$ 。
对于所有 i 使得 $a_i ≥ a_p$ ，让 $a_i ← a_i - 2(a_i - a_p)$ 。

例如，如果原始数组是 [2，4，5，3]，而您选择 p = 2 并执行操作 1，则数组将变为 [6，4，5，5]

现在，您希望通过这些操作来最小化数组的范围。回想一下，数组的范围是数组的最大元素和最小元素之间的差值。

思路

还是一道思维题（感觉本场的思维题特别多

Inspired by 命题组

先直接给出答案：将输入数组 $a$ 排序后，答案为 $g$ = $gcd(a_2-a_1,a_3-a_2,...,a_n-a_{n-1})$
证明 Step1：

首先说明答案不会比 $g$ 小：考虑差分数组 $d_i$ = $a_{i 1}-a_i(i\leq n-1)$ ，则初始 $d_i$ 都是 $g$ 的倍数，因此每个数都可以表示成 $a_i$ = $a_1 k_ig$ 的形式。那么在一次操作之后，容易说明每个数依然可以表示为 $a_i'$ = $a_1 k_i'g$ 的形式，不难看出它们排序后求相邻项之差的 gcd 仍然形如 $kg$ ，不会更小。
证明 Step2：
- 接下来说明总能达到 $g$ ，即若当前极差还不是 $g$ ，我们总有一种操作能将极差减小：记当前数组先去重再排序得到的 $k$ 个数组是 $b_1,...,b_k$ ， $k\geq 3$ 时选择下标 $p$ = $k-1$ 执行操作2，一定可以减小极差。
- $k$ = $2$ 时：说明此时已经做到极差 $g$ 了，无需再操作。为什么此时极差不会是 $kg(k>1)$ ？这是因为上述操作完全不改变操作前后的 $g$ ，Step1 已经证明不会小于 $g$ ，接下来证明不会大于即可：
- 操作后 $g$ = $gcd(b_2-b_1,b_3-b_2,...,b_{k-1}-b_{k-2})$ ，少了一项 $b_k-b_{k-1}$ ，但其实操作后 $b_{k-1}-b_k'$ = $b_k-b_{k-1}$ ，所以这项也还在，因此 $g$ 不会更大。证毕！

AC代码

时间复杂度：O( $Tn$ )

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int infmin = 0xc0c0c0c0;
const int infmax = 0x3f3f3f3f;
const int maxn = 1e5 + 10;

ll num[maxn];

inline bool cmp(ll a, ll b) {
    return a < b;
}

// 【GCD】
ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> num[i];
        }
        sort(num + 1, num + n + 1, cmp);
        
        if(num[n]-num[1]==0 || n==1){
            cout << 0 << "\n";
            continue;
        }

        ll ans = 0;

        for (int i = 2; i <= n; i++) {
            ans = gcd(ans, num[i] - num[i - 1]);
        }

        cout << ans << "\n";
    }

    return 0;
}