多好的一道思维题！

蒟蒻觉得大佬们双指针贪心部分讲得有些简略，故写一篇题解来具体说说自己的想法。

首先，我们要发现一个重要的性质：记最终的答案为 $ans$，那么 $ans$ 一定整除 $\sum_{i=1}^{n} A_i$。因为无论怎么操作序列的和都不变，且最后必须保证 $ans$ 是所有 $A_i$ 的公约数。

那么，我们记 $sum=\sum_{i=1}^{n} A_i$，则 $ans$ 一定是 $sum$ 的因子。那就需要枚举 $sum$ 的因子，合法的最大因子就是 $ans$。

接下来就是判断是否合法。当考察因子 $x$ 时，考虑记录每个 $B_i=A_i \bmod x$，并将它们从小到大排序，接着进行双指针扫描，贪心地计算所需操作次数 $cnt$，若 $cnt\le k$ 则合法。记左指针为 $l$，右指针为 $r$，具体贪心实现如下：

• 若 $B_l+B_r=x$，那么操作 $B_l$ 次 $B_l,B_r$ 就可以都变成 $0$，$cnt$ 加上 $B_l$，两个指针都向中间靠 $1$ 个坐标。

• 若 $B_l+B_r<x$，那么钦定操作 $B_l$ 次使得 $B_l$ 变成 $0$，则 $B_r$ 变成 $B_r+B_l$，$cnt$ 加上 $B_l$，左指针向中间靠 $1$ 个坐标。

• 若 $B_l+B_r>x$，那么钦定操作 $x-B_r$ 次使得 $B_r$ 变成 $x$，相当于变成 $0$，则 $B_l$ 变成 $B_l-x+B_r$，$cnt$ 加上 $x-B_r$，右指针向中间靠 $1$ 个坐标。

如果你对后两个操作有疑问，如“为什么要这样钦定”，请代入前提条件“已经将 $B_i$ 从小到大排序”。

那么本题就完成了，时间复杂度是 $O(n\log n\sqrt {sum})$。但实际上肯定要比这个快，因为 $O(n\log n)$ 是检查因数时排序的复杂度。

#include <bits/stdc++.h>
#define i64 long long 
const int N = 505; 
using namespace std;
int n, k, a[N]; 
i64 sum, ans, b[N]; 
bool chk(i64 x) {
	for(int i = 1; i <= n; i++) b[i] = 1ll * a[i] % x; 
	sort(b + 1, b + n + 1); 
	int l = 1, r = n; 
	i64 cnt = 0; 
	while(l <= r) {
		if(b[l] + b[r] == x) cnt += b[l], l++, r--; 
		else if(b[l] + b[r] < x) cnt += b[l], b[r] += b[l], l++; 
		else if(b[l] + b[r] > x) cnt += x - b[r], b[l] -= (x - b[r]), r--;  
		if(cnt > k) return false;  
	} 
	return cnt <= k; 
} 
int main(){
	scanf("%d %d", &n, &k); 
	for(int i = 1; i <= n; i++) {
		scanf("%d", &a[i]); 
		sum += a[i]; 
	} 
	for(i64 i = 1; i * i <= sum; i++) {
		if(sum % i == 0) {
			if(i > ans && chk(i)) ans = i; 
			if(sum / i > ans && chk(sum / i)) ans = sum / i; 
		}
	} 
	printf("%lld\n", ans); 
	return 0;
}