题目链接

知识点：扩展欧几里得算法，不定方程
因为觉得官方的题解写的不明所以，所以写了这篇题解。

不妨设最终每个数的值为 ，操作数为 ，数组的和为 ，数组中的最大值为 ，最小值为 ， 。则有 。

接下来，先用扩展欧几里得求一下这个方程的解，如果无解直接输出 -1。这里还要特判一下 的情况，这种情况下，除非每个数相同，否则都是 -1。现在我们求得了一组解 ，要怎么求最小的 呢？

首先，如果 ，则考虑增大 的同时减小 。具体地，令 为最大的非负整数满足 ，则使 ，。否则， 不需要减小。

接着，因为每次操作不能将一个 减很多次，则 ；因为不能执行加操作，所以 。上面那组不定方程的整数解可以表示为 ，带入到这两个不等式中，可以得到两个与 有关的不等式，分别是 和 。解一下就可以得到 的下界，注意向上取整的问题。然后，我们就可以愉快地得到 的最小值了。

代码如下：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+5;
int n, k;
ll sum, mx, mn;
inline void chkmx(ll &x, ll y){
	x = x>y?x:y;
}
inline void chkmn(ll &x, ll y){
	x = x<y?x:y;
}
int ex_euclid(int a, int b, ll c, ll &x, ll &y){
	if(b == 0){
		x=c/a, y=0;
		if(c%a != 0) return -1;
		return a;
	}
	int g;
	ll xx, yy;
	g = ex_euclid(b,a%b,c,xx,yy);
	x=yy, y=xx-a/b*yy;
	return g;
}

int main(){
	scanf("%d%d", &n, &k);
	int g, a, b;
	ll x, y, t=0;
	mn = 1e9+1;
	for(int i=1; i<=n; ++i){//因为只有最大值、最小值和总和有用，所以不需要存下整个数组
		scanf("%lld", &x);
		sum += x;
		chkmx(mx,x); chkmn(mn,x);
	}
	if(mx == mn){
		printf("0\n"); return 0;
	}else if(n == k){
        printf("-1\n"); return 0;
    }

	g = ex_euclid(n,k,sum,x,y);
	if(g == -1){//裴蜀定理，判断是否有解
		printf("-1\n"); return 0;
	}

	a=n/g, b=k/g;
	if(x < mn){//确保最开始的时候y足够小 
		t = (mn-x)/b;
		x+=b*t, y-=a*t;
		t = 0;
	}
	if(y < 0)//y>=0
		chkmx(t, (-y-1)/a+1);
	if(x > mn)//最终得到的数x0应该不大于最小值mn
		chkmx(t, (x-mn-1)/b+1);
	if(mx > x+y)//对最大值减一的次数不超过y次
		chkmx(t, (mx-x-y-1)/(a-b)+1);
	y += a*t;
	printf("%lld\n", y);
	return 0;
}/*
5 4
1 2 3 5 5
output:9
7 6
2 2 3 4 5 6 8
output:26
*/