题解 | #一道GCD问题#

加同一个数不改变差值 对于任意两个下标 $i, j$ 都有 $(a_i+k)-(a_j+k)=a_i-a_j$ 因此，经过加法后的所有数的任何公约数必须同时整除原来的所有差值 $a_i-a_j$ 。
可实现的 $\text{gcd}$ 必为差值的最大公约数的约数 记 $G=\text{gcd}(\{|a_i-a_j| \mid 1\le i<j\le n\})$ 任何一个满足 $\text{gcd}(a_1+k, \dots, a_n+k)=d$ 的整数 $d$ 必须整除所有的差值，从而 $d \mid G$ . 于是可得到的最大可能的 $\text{gcd}$ 正好是 $G$ 本身。
如何求出对应的 $k$ 由于 $G$ 是所有差值的公约数，所有原始数在模 $G$ 意义下具有相同的余数 $r\equiv a_1\equiv a_2\equiv\cdots\equiv a_n \pmod{G}$ 为了让所有数都变成 $G$ 的倍数，只需把每个数再加 $(G-r)$ （模 $G$ 的最小非负解），即 $k_{\min}= (G-r)\bmod G,\quad \text{其中 } r=a_1\bmod G$ 此时 $a_i+k_{\min}\equiv r+(G-r)\equiv0 \pmod{G}$ 故 $\text{gcd}(a_1+k_{\min}, \dots, a_n+k_{\min})=G$ . 又因任何满足条件的 $k$ 必须满足同余式 $k\equiv -r \pmod{G}$ ， $(G-r)\bmod G$ 正是最小的非负整数解。

综上，最大的可能 $\text{gcd}$ 就是所有两两差值的最大公约数 $G$ ，而得到它的最小 $k$ 为 $(G-a_1\bmod G)\bmod G$ 。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    sort(a.begin(), a.end());
    ll g = a[1] - a[0];
    for (int i = 2; i < n; i++) {
        g = gcd(g, a[i] - a[0]);
    }
    ll r = a[0] % g;
    ll k = (g - r) % g;
    cout << g << " " << k << endl;
}