答案大于max{ai}可以直接计算
主要考虑小于的情况
直接计算gcd很困难，不妨枚举x|gcd
那么对于ai来说
假设 x(k-1)<ai<=xk,那么
ai就需要xk-ai次操作，那么我们对于一个x，只需枚举k计算区间数的个数即可算出需要的操作数。
复杂度O(nlnn)
这种套路就是取模转化成减法后，进行区间维护。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<set>
#include<map>
#define A puts("Yes")
#define B puts("No")
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
using namespace std;
typedef double db;
typedef long long ll;
// const ll mo = 998244353;
const int inf = 1e9;
const int N = 1e6 + 5;
const int M = 3e5 + 5;
ll a[N], s[N], n, k, ans, tot, lim, mx;
int main()
{
// #ifdef LOCAL
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// #endif
scanf("%lld %lld", &n, &lim);
fo(i, 1, n) scanf("%lld", &a[i]), s[a[i]]++, tot += a[i], mx = max(mx, a[i]);
fo(i, 1, N - 1) s[i] += s[i - 1];
fo(x, 1, 3e5) { //
ll sum = 0;
fo(k, 1, 3e5 / x + 1) {
sum += k * x * (s[min(k * x, (ll)N - 1)] - s[(k - 1) * x]);
}
// printf("%lld\n", sum);
if (sum - tot <= lim) ans = max(ans, x);
}
if (lim >= mx * n - tot) {
ans = max(ans, mx + (lim - (mx * n - tot)) / n);
}
printf("%lld", ans);
return 0;
}