我们可以把该题分为两个模块：

  1. 如何通过给定的数组，算出得到最大公约数 g
  2. 如何根据 g 或者 直接 求出k

对于问题1，我们不难发现

当 g | (ai + k) 且 g | (aj + k) 时， g | (ai+k) - (aj+k) = g | (ai-aj)

前者为mg，后者为ng，最后两者相减为 (m-n)g，依旧可以被 g 整除

所以能得出重要性质：g 这个最大公约数，可以整除数组中任意两个数的差值

同时，当 g | (ai - a1) 且 g | (aj - a1) 时，同理能够得到 g | ai - a1 - aj + a1 = g | ai - aj

所以只要求出所有数和a1的差值的最大公约数，这个最大公约数就可以作为所有数对的差值的最大公约数

因此，只需要求出gcd((a1-a1),(a2-a1),(a3-a1),(a4-a1),……,(an-a1))即可

对于问题2，我们此时已经得到了 a1 + k = mg 中的 a1 与 g ，所以可以先去思考是否可以通过这个关系式得到 k

假设 a1 % g = r，那就有 mg + r = a1；又 g | a1 + k ，所以 g | mg + r + k

mg 肯定能够被 g 整除，所以我们现在只需要满足 r + k 可以被g整除即可，所以我们可以得到：

r + k = ng ( n = 1,2,3,……)

当 r = 0 时，a1 可以直接被 g 整除，此时 k = 0

当 r != 0 时，要求 k 最小，那么此时 n 取 1，所以 k = g - r

剩下的注意点：

  • 求 gcd 时，我们要保证差值为正，这样用 gcd 函数才能求出正确的解；所以我们可以排序，让 a1 = 数组最小值
  • gcd 用辗转相除法来求

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1e6 + 10;
int a[N];

int gcd(int a,int b)
{
	return b == 0 ? a : gcd(b,a%b);
}

signed main()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	sort(a+1,a+n+1,less<int>());
	int x = gcd(0,a[2]-a[1]);
	for(int i=3;i<=n;i++)
		x = gcd(x,a[i]-a[1]);
	//x即为最大公约数
	int r = a[1] % x;
	if(!r) cout<<x<<" "<<0;
	else cout<<x<<" "<<(x-r); 
	return 0;
}