一道GCD问题

题目链接：nowcoder 213804

到主站看：https://blog.csdn.net/weixin_43346722/article/details/112734928

题目大意

有一堆数，你要把他们都加一个尽可能小的数 k，让它们的 gcd 尽可能大。
要你输出这个 k 和最后最大的 gcd。

思路

这道题让所有数都加一个数，那他们任意两个数的差都是一样的。

那我们再看看 gcd，如果一堆数的 gcd 是 x，那任意两个数的差的绝对值一定是 x 的倍数。

那我们不如求出这些数排序后，每两个数之间的差组合成一个新的序列，这个序列的 gcd 就是它们可以有的最大的 gcd。

那 k 应该最小要多少呢？
那就是要让每个都变成我们求出 gcd 值的倍数。
那其实我们只要让最小的加到它的倍数就可以了。
（那当然如果 gcd 是 的话就不用加了）

代码

#include<cstdio>
#include<algorithm>

using namespace std;

int n, a[100010], re, zf, gcdd;
char c;

int read() {
    zf = 1;
    re = 0;
    c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') zf = -zf;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        re = re * 10 + c - '0';
        c = getchar();
    }
    return re * zf;
}

bool cmp(int x, int y) {
    return x < y;
}

int gcd(int x, int y) {
    if (!y) return x;
    return gcd(y, x % y);
}

int main() {
    n = read();
    for (int i = 1; i <= n; i++) {
        a[i] = read();
    }

    sort(a + 1, a + n + 1, cmp);

    gcdd = a[2] - a[1];
    for (int i = 3; i <= n; i++) {
        gcdd = gcd(gcdd, a[i] - a[i - 1]);
    }

    if (gcdd == 1) printf("1 0");
        else printf("%d %d", gcdd, gcdd - (a[1] % gcdd));

    return 0;
}