Codeforces VK Cup Finals #424 Div.1 C. Bamboo Partition（数论）

　　题目要求符合以下条件的最大的d

　　化简得

　　注意到

　　最多只有2*sqrt(a[i]-1)种取值，也就是一共最多有n*sqrt(10^19)种取值，于是枚举一下d，计算出符合上上式的最大的d更新答案，然后d跳跃到下一个取值

　　效率O(n²sqrt(10^9))

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
const int maxn=110,inf=1e9;
ll n,k,ans,r;
ll a[maxn];
void read(ll &k)
{
    int f=1;k=0;char c=getchar();
    while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
    while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar();
    k*=f;
}
int main()
{
    read(n);read(k);
    for(int i=1;i<=n;i++)read(a[i]),k+=a[i];
    for(ll d=1;d<=1000000000;d=r+1)
    {
        r=1ll*10000*inf;
        for(int i=1;i<=n;i++)if(a[i]>d)r=min(r,(a[i]-1)/((a[i]-1)/d));
        ll tot=0;for(int i=1;i<=n;i++)tot+=(a[i]-1)/d+1;
        ll mxd=k/tot;if(d<=mxd&&mxd<=r)ans=max(ans,mxd);
    }
    printf("%lld
",ans);
    return 0;
}