算法

(贪心) $O(\sqrt{N\max\{A\}} * N\log N)$

注意到，无论对序列怎样操作它的总和一直不变，此外，如果 $x$ 能整除所有的数意味着，它必然能整除序列总和。

所以问题就转化成了将所有数变成 $x$ 的倍数需要多少次操作。

我们可以先筛出序列总和 $sum$ 的所有因子.
对于每个因子 $d$，我们可以让序列中所有的数对 $d$ 取余变为 $r_i$，并对其进行排序，然后可以注意到这样的事实：

如果把所有的 $r_i$ 的符号变为 '+'，那么所有数的和 $tot$ 都是 $d$ 的倍数，而一旦有一个数的符号变为 '-'，意味着总和将少一个 $d$，所以 '-' 与 '+' 的分界线就是 $N - \frac{tot}{d}$

于是，将所有数变成 $d$ 的倍数所需要的操作次数就是在这个分界线之前的所有 $r_i$ 的和。

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::max;
using std::min;
using std::set;
using std::vector;
using ll = long long;

int main() {
    int n, k;
    cin >> n >> k;

    vector<int> a(n);
    rep(i, n) cin >> a[i];

    ll sum = 0;
    rep(i, n) sum += a[i];

    set<ll> candidates;
    for (int i = 1; i * i <= sum; ++i) {
        if (sum % i == 0) {
            candidates.insert(i);
            candidates.insert(sum / i);
        }
    }

    ll ans = 1;
    for (ll x : candidates) {
        ll need;
        { // calc need
            vector<ll> r(n);
            rep(i, n) r[i] = a[i] % x;
            sort(r.begin(), r.end());
            ll tot = 0;
            rep(i, n) tot += r[i];
            int l = n - tot / x;
            need = 0;
            rep(i, l) need += r[i];
        }
        if (need <= k) ans = max(ans, x);
    }

    cout << ans << '\n';

    return 0;
}