\(9.1\)
鸽。
\(9.2\)
模拟赛。
难度大概是 \([2300,2400]+[2900,3300]+?\)。
- \(\text{A}\)：
给定一个正整数序列 \(\{a_n\}\)，和一个初始全 \(0\) 的整数序列 \(\{b_n\}\)，每单位时间 \(\forall i\in [1,n],b_i\gets b_i+1\)。
定义对于 \(b_j\) 的一次操作为操作后该 \(b_j\) 不再执行 \(b_j\gets b_j+1\) 操作。
求一个最大的 \(k\) 满足：可以每隔 \(k\) 单位时间做若干次个 \(b_i\) 进行操作，使得最终 \(b_i\ge a_i\) 且 \(\sum\limits_{i=1}^n b_i-a_i<m\)。
\(n\le100,a_i\le10^9,m\le10^{11}\)。
显然我们对于 \(a_i\) 要求不小于 \(a_i\) 的最小的 \(b_i\)，易得 \(b_i=\lceil \frac{a_i}{k}\rceil\Rightarrow b_i-a_i=(-a_i)\bmod{k}\)。
即题目转换为求最大的 \(k\) 使得 \(\sum\limits_{i=1}^m ((-a_i)\bmod{k})<m\)。
考虑单调性，但这个柿子显然没有单调性。
考虑为什么没有单调性，\(a=bq+r\Rightarrow r=a-bq\)，由于 \(a\) 均为常数，所以 \(r\) 的值由 \(bq\) 决定，\(bq=\lfloor \frac{a}{b}\rfloor b\)。设 \(b'>b\)，则当 \(\lfloor \frac{a}{b}\rfloor=\lfloor \frac{a}{b'}\rfloor\) 时 \(b'q>bq\Rightarrow r'<r\)。也就是说，当 \(\lfloor \frac{a}{b}\rfloor\) 相同时，\(a\bmod{b}\) 具有单调性。
考虑整除分块，对于 \(a\)，其 \(\lfloor \frac{a}{b}\rfloor\) 的值至多只有 \(\sqrt{a}\) 个。
则我们对于每个 \(a_i\) 做一个整除分块，然后把所有使得 \(\lfloor \frac{a_i}{b}\rfloor\) 的 \(b\) 丢到一个 vector 里面，然后排个序去个重，对于所有的 \(k\in [t_i,t_{i+1}]\) 原式具有单调性，二分即可。
复杂度 \(\Theta(n\sqrt{V}\log V)\)。
- \(\text{B}\)：
Too Hard。
- \(\text{C}\)：
Too Hard。