题意：
给定 n , M n,M n,M, { h n } \{h_n\} {hn?}，求最大的 k k k，满足 ∑ i = 1 n k ? ( ( h i ? 1 ) ? m o d ? k + 1 ) < M \sum_{i=1}^n k-((h_i-1) \bmod k +1) < M ∑i=1n?k?((hi??1)modk+1)<M。其中 n ≤ 100 , M ≤ 1 0 11 , h i ≤ 1 0 9 n\leq100,M\leq 10^{11},h_i\leq 10^9 n≤100,M≤1011,hi?≤109
题解：
虽然有非常简单的做法，但是这是还是要提一个思路清奇巧妙 考场上没想到sb做法 的做法。
考虑拆式子：
∑
i
=
1
n
k
?
(
(
h
i
?
1
)
?
m
o
d
?
k
+
1
)
\sum_{i=1}^n k-((h_i-1) \bmod k +1)
∑i=1n?k?((hi??1)modk+1)
=
n
k
?
n
?
∑
i
=
1
n
(
(
h
i
?
1
)
?
m
o
d
?
k
)
=nk-n-\sum_{i=1}^n ((h_i-1) \bmod k)
=nk?n?∑i=1n?((hi??1)modk)，令
x
i
=
h
i
?
1
x_i=h_i-1
xi?=hi??1
=
n
k
?
n
?
∑
i
=
1
n
(
x
i
?
m
o
d
?
k
)
=nk-n-\sum_{i=1}^n (x_i \bmod k)
=nk?n?∑i=1n?(xi?modk)
=
n
k
?
n
?
∑
i
=
1
n
(
x
i
?
k
×
?
x
i
k
?
)
=nk-n-\sum_{i=1}^n (x_i-k \times \lfloor \frac{x_i}{k}\rfloor )
=nk?n?∑i=1n?(xi??k×?kxi???)
n
k
?
n
?
∑
i
=
1
n
x
i
+
k
×
∑
i
=
1
n
?
x
i
k
?
≤
M
?
1
nk-n-\sum_{i=1}^n x_i+k \times \sum_{i=1}^n\lfloor \frac{x_i}{k}\rfloor \leq M-1
nk?n?∑i=1n?xi?+k×∑i=1n??kxi???≤M?1
即：
n
k
+
k
×
∑
i
=
1
n
?
x
i
k
?
≤
M
?
1
+
n
nk+k\times \sum_{i=1}^n\lfloor \frac{x_i}{k}\rfloor \leq M-1+n
nk+k×∑i=1n??kxi???≤M?1+n
n
+
∑
i
=
1
n
?
x
i
k
?
≤
?
M
?
1
+
n
k
?
n+\sum_{i=1}^n\lfloor \frac{x_i}{k}\rfloor \leq \lfloor \frac{M-1+n}{k} \rfloor
n+∑i=1n??kxi???≤?kM?1+n??
然后对 ? M ? 1 + n k ? \lfloor \frac{M-1+n}{k} \rfloor ?kM?1+n?? 数论分块，每次就相当于求出在 [ l , r ] [l,r] [l,r] 内的 k k k 的最大值满足 ∑ i = 1 n ? x i k ? ≤ ? M ? 1 + n k ? ? n \sum_{i=1}^n\lfloor \frac{x_i}{k}\rfloor \leq \lfloor \frac{M-1+n}{k} \rfloor-n ∑i=1n??kxi???≤?kM?1+n???n，该式子右边的值是固定的，所以我们只需要考虑左边即可，即 ∑ i = 1 n ? x i k ? \sum_{i=1}^n \lfloor \frac{x_i}{k} \rfloor ∑i=1n??kxi??? 如何快速求出区间内小于某个值得最靠右的位置。
考虑到 ? x i k ? \lfloor \frac{x_i}{k}\rfloor ?kxi??? 的值只有 x i \sqrt{x_i} xi?? 种，所以我们对于 ? x i k ? = j \lfloor \frac{x_i}{k}\rfloor=j ?kxi???=j 的 k k k 所在的区间都加上 j j j，然后我们只需要查询前 i i i 个位置小于等于某个值的最靠右的位置即可，可以将询问 [ l i , r i ] [l_i,r_i] [li?,ri?] 离线下来，然后扫描线维护，每次加入一个新的位置，用数据结构求出该点位置的值，然后去维护一个单调栈即可求出小于等于某个值的最靠右的位置，离散化一下即可。
考虑效率：预处理 ? x i k ? \lfloor \frac{x_i}{k}\rfloor ?kxi??? 的部分效率为 O ( n l o g n × m a x { x i } × m a x { x i } ) O(nlog_{n\times \sqrt{max\{x_i\}}}\times \sqrt {max\{x_i\}}) O(nlogn×max{xi?}??×max{xi?}?)，询问部分效率为 O ( M ) × l o g n × m a x { x i } O(\sqrt{M}) \times log_{n\times \sqrt{max\{x_i\}}} O(M?)×logn×max{xi?}?? 约为 O ( x i × n l o g ( n × x i ) ) O(\sqrt{x_i} \times nlog(n\times \sqrt{x_i})) O(xi??×nlog(n×xi??))，可能会 T L E TLE TLE，所以考虑分类，小于 S S S 的 k k k 暴力 O ( n ) O(n) O(n) 遍历，大于 S S S 的 k k k 采取上述策略。
暴力部分效率： O ( S n ) O(Sn) O(Sn)
另一个做法的效率： O ( n l o g × ? x i S ? ) O(nlog\times \lfloor \frac{x_i}{S}\rfloor) O(nlog×?Sxi???)
平衡一下效率：
S
n
=
n
l
o
g
×
?
x
i
S
?
Sn=nlog\times \lfloor \frac{x_i}{S}\rfloor
Sn=nlog×?Sxi???
解得，
S
=
1
0
5
S=10^5
S=105
实测能过
代码
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=105;
const int S=100000;
const int MAXN=4e6+10;
int n,h[N],mx;
LL m,ans;
struct Node{
LL l,r,d;
}jia[MAXN],qu[MAXN];
int tot,tot_j,tot_q,c[MAXN<<1];
LL b[MAXN<<1];
vector<pair<int,int> > q[MAXN<<1];
int sta[MAXN<<1],st,val[MAXN<<1];
inline int lowbit(int x){return x&(-x);}
inline void add(int x,int d){
for(;x<=tot;x+=lowbit(x))c[x]+=d;
}
inline int ask(int x){
int s=0;
for(;x;x-=lowbit(x))s+=c[x];
return s;
}
int main(){
scanf("%d%lld",&n,&m);m+=n-1;
for(int i=1;i<=n;++i)scanf("%d",&h[i]),h[i]--,m+=h[i],mx=max(mx,h[i]);
sort(h+1,h+n+1);
for(int i=1;i<=S;++i){
LL s=1ll*n*i;
for(int j=1;j<=n;++j)s+=1ll*(h[j]/i)*i;
if(s<=m)ans=i;
}
if(mx<=S){
printf("%lld\n",ans);
return 0;
}
for(int i=1;i<=n;++i){
if(h[i]<S)continue;
for(int l=S+1,r;l<=h[i];l=r+1){
r=h[i]/(h[i]/l);
b[++tot]=l,b[++tot]=r;
jia[++tot_j]=(Node){l,r,(h[i]/l)};
}
}
for(LL l=S+1,r;l<=m;l=r+1){
r=m/(m/l);
b[++tot]=l,b[++tot]=r;
qu[++tot_q]=(Node){l,r,(m/l)-n};
}
sort(b+1,b+tot+1);
tot=unique(b+1,b+tot+1)-b-1;
for(int i=1;i<=tot_j;++i){
int L=lower_bound(b+1,b+tot+1,jia[i].l)-b;
int R=lower_bound(b+1,b+tot+1,jia[i].r)-b;
add(L,jia[i].d);
add(R+1,-jia[i].d);
}
for(int i=1;i<=tot_q;++i){
int L=lower_bound(b+1,b+tot+1,qu[i].l)-b;
int R=lower_bound(b+1,b+tot+1,qu[i].r)-b;
q[R].push_back(make_pair(L,qu[i].d));
}
for(int i=1;i<=tot;++i){
val[i]=ask(i);
while(st&&val[sta[st]]>=val[i])st--;
sta[++st]=i;
for(auto k:q[i]){
int L=k.first,d=k.second;
int l=1,r=st;
while(l<r){
int mid=(l+r+1)>>1;
if(val[sta[mid]]<=d)l=mid;
else r=mid-1;
}
if(st>=l&&val[sta[l]]<=d&&sta[l]>=L)ans=max(ans,b[sta[l]]);
}
}
printf("%lld\n",ans);
return 0;
}
