以下令 $amax=\max_{i=1}^n{a_i}$。
分类讨论：
如果能用 $K$ 次将其全部补到 $amax$，那当然最好。如果 $K$ 还没有用完，那就接着补齐，可以证明此时的 $\gcd$ 一定最大。
否则，这个数列的 $\gcd$ 一定不会超过 $amax$，枚举这个 $\gcd$ 从 $amax$ 到 $1$，很简单做出 $O(amax \times n)$ 的做法。
怎么办呢？设现在枚举到 $x$，注意到 $a$ 中的数一定在区间 $(0,x],(x,2x],(2x,3x]...(kx,n]$中的一个，前缀和优化就可以做到 $O(\frac{n}{x})$ 检查。
总复杂度 $O(nlogn)$。

#include<bits/stdc++.h>
#define copying using
#define is namespace
#define shameless std
#define int long long
copying is shameless;
int n,total;
int k;
int a[300005];
int t[300005],pret[300005];
signed main(){
    scanf("%lld%lld",&n,&k);
    int maxval=0;
    for(int i=1;i<=n;i++){
        scanf("%lld",a+i);
        ++t[a[i]];
        total+=a[i];
        maxval=max(maxval,a[i]);
    }
    int diff=0;
    for(int i=1;i<=n;i++){
        diff+=maxval-a[i];
    }
    if(k>=diff){
        printf("%lld",maxval+(k-diff)/n);
        exit(0);
    }
    for(int i=1;i<=maxval;i++){
        pret[i]=t[i]+pret[i-1];
    }
    for(int i=maxval;i>1;i--){
        int ans=0;
        int x;
        for(x=i;x-i<maxval;x+=i){
            if(x<=maxval)ans+=(pret[x]-pret[x-i])*x;
            else ans+=(n-pret[x-i])*x;
        }
        ans-=total;
        if(ans<=k)printf("%lld",i),exit(0);
    }
    puts("1");
    return 0;
}