原题链接
- 题解:解决了历史遗留问题。很显然的是,这样操作总和不会变,然后所有 (gcd) 的可能的取值都是会是 (sum) 的因子,所以可以 (O(sqrt {sum})) 的时间复杂度来枚举 (gcd),然后 (O(n)) 遍历用最小操作来看是否是小于 (k),最后取最大。
- 代码:
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
const ll N = 1e6 + 9, mod = 1e9 + 7;
ll a[N];
ll b[N];
ll sum = 0;
ll n, k;
ll ans;
void check(ll p) {
ll ssum = 0;
for (ll i = 1; i <= n; i++) {
b[i] = a[i] % p;
}
sort(b + 1, b + 1 + n);
ll sub = 0;
ll add = 0;
int l = 1, r = n;
while (l <= r) {
while (l <= r && b[l] == 0) {
l++;
}
while (l <= r && b[r] == p) {
r--;
}
if (r == l) {
ssum += min(b[l], p - b[l]);
break;
}
if (l > r) break;
ssum += b[l];
ll t = b[l];
b[l] = 0;
while (l <= r && t > 0) {
if ( b[r] + t >= p ) {
t -= (p - b[r]);
b[r] = p;
r--;
} else {
b[r] += t;
t = 0;
break;
}
}
}
if (ssum <= k) {
ans = max(ans, p);
}
}
signed main() {
cin >> n >> k;
for (ll i = 1; i <= n; i++) {
cin >> a[i];
sum += a[i];
}
ans = -1;
check(sum);
for (ll i = 1; i * i <= sum; i++) {
if (sum % i == 0) {
check(i);
check(sum / i);
}
}
cout << ans << endl;
return 0;
}