原文链接https://www.cnblogs.com/zhouzhendong/p/CF830C.html
题解
把问题转化成求最大的 $d$ ，满足
$$\sum_{1\leq i \leq n}(\lceil a_i / d\rceil \times d - a_i )\leq k$$
移项
$$(d\sum_{1\leq i \leq n } \lceil a_i / d \rceil )\leq k + \sum_{1\leq i \leq n} a_i$$
于是可能的 $d$ 就只可能有 $O(\sqrt{k+\sum_{1\leq i \leq n} a_i})$ 种。直接暴力枚举并判断就好了。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
LL read(){
LL x=0,f=1;
char ch=getchar();
while (!isdigit(ch)&&ch!='-')
ch=getchar();
if (ch=='-')
f=0,ch=getchar();
while (isdigit(ch))
x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return f?x:-x;
}
const int N=105;
int n;
LL k;
int a[N];
int check(LL x){
LL tot=0;
for (int i=1;i<=n;i++)
tot+=x*((a[i]+x-1)/x);
return tot<=k;
}
int main(){
n=read(),k=read();
for (int i=1;i<=n;i++)
k+=a[i]=read();
LL ans=1;
for (LL i=sqrt(k)+1;i>=1;i--){
if (check(i))
ans=max(ans,i);
if (check(k/i))
ans=max(ans,k/i);
}
cout << ans;
return 0;
}