玩原神玩的

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define int long long
#define F(i,x,y) for(int i=x;i<=y;++i)
#define G(i,x,y) for(int i=x;i>=y;--i)
#define FD(i,x,y) for(int i=x;i*i<=y;++i)
#define GD(i,x,y) for(int i=x;i*i>=y;--i)
#define adde(x,y) z[x].eb(y);
#define Adde(x,y) z[x].eb(y),z[y].eb(x);
#define addew(x,y,w) z[x].eb(y,w)
#define Addew(x,y,w) z[x].eb(y,w),z[y].eb(x,w)
#define FIMX(X) memset(X,0x3f,sizeof X)
#define FIMI(X) memset(X,-0x3f,sizeof X)
#define FI0(X) memset(X,0,sizeof X)
#define FIN(X) memset(X,-1,sizeof X)
#define rng(X) X.begin(),X.end()
#define PII pair<int,int>
#define PDD pair<double,double>
#define PIII tuple<int,int,int>
#define VI vector<int>
#define VII vector<PII>
#define VID vector<pair<int,double>>
#define VDD vector<PDD>
using namespace std;
const int N=1000010,mod=1e9+7;
int a[N],n,k,b[N];
//判断是否可以分为x个一组
int chk(int x){
    int s=accumulate(a+1,a+n+1,0ll);
    if(x>k){
        //已知当前和为s
        //问如果加0~k则s是否可以为x的倍数
        if(s%x>(s+k)%x||s%x==0);
        else return 0;
    }
    int lim=(s+k)/x*x-s;
    //可以添加lim个元素
    //判断当前出现次数最多的卡是否可以不超过 n/x
    //即a[1]<=(n+lim)/x;
    int ji=(s+lim)/x;
    // F(i,1,n)cout<<a[i]<<' ';cout<<'\n';
    // if(a[1]<=ji)return 1;
    G(i,n-1,1){
        int diff=(a[i]-a[i+1])*(n-i);
        if(diff<=lim){
            lim-=diff;
            a[i+1]=a[i];
        }else{
            int sh=lim/(n-i);
            int liu=lim%(n-i);
            //前liu个元素额外增加 1
            F(j,i+2,n)a[j]=a[i+1];
            F(j,i+1,n)a[j]+=sh;
            for(int j=i+1,fi=1;j<=n&&fi<=liu;++j,++fi)++a[j];
            lim=0;
            break;
        }
    }
    if(lim){
        int sh=lim/n,liu=lim%n;
        F(i,1,n)a[i]+=sh;
        F(i,1,liu)++a[i];
    }
    // F(i,1,n)cout<<a[i]<<' ';
    // cout<<'\n';
    // cout<<"qwq "<<lim<<' '<<ji<<'\n';
    if(a[1]<=ji)return 1;
    return 0;
}
void solve(unsigned __testid=1){
    cin>>n>>k;
    F(i,1,n)cin>>a[i];
    sort(a+1,a+n+1,greater<int>());
    F(i,1,n)b[i]=a[i];
    // cout<<chk(3)<<'\n';
    // return;
    //若当前出现次数最多的卡不超过 n/x 且总卡数量为 x 的倍数 则答案可以为 x
    int l=1,r=n+k,best=-1;
    while(l<=r){
        int mid=l+r>>1;
        if(chk(mid))best=mid,l=mid+1;
        else r=mid-1;
        F(i,1,n)a[i]=b[i];
    }
    cout<<best<<'\n';
    // cout<<"chk: "<<chk(2)<<'\n';
}
void Presolve() {
    
}
int32_t main(){
    int T;
    // T=1;
    cin>>T;
    Presolve();
    F(_,1,T)
        solve(_);
    return 0;
}

wa on pretest #4