只要有信念，就一定能成功！
- 加强前，这道题是一道不可多得的好题。
- 加强后，这道题是一道在阳间不可多得的好题。
当然出到互测里还是显得太水了。
题意
- 下面定义 $w$ 为 $v_i,a_i$ 的值域范围。
- 如果没有明确说明，下面的 $v_i$ 是指分配后的结果。
分析
一个显然的贪心思路是 $a_1,a_n$ 分配给 $v_1$，此后将不考虑这两个量。
发现该问题具有可二分性，二分答案 $k$ 之后问题变成：考虑无限可重集 $\{v_i/j\mid i\in[1,n],j\in\mathbf{Z^{+}}\}$让 $>v_1/k$ 的数个数最少。
对于一个设置完成的 $v_i$，它会给答案增加 $\lfloor (v_ik-1)/v_1\rfloor$ 的贡献，然后就有个 $01$ 背包的做法，设 $f(i,j)$ 表示考虑到前 $i$ 个数，给第 $i+1$ 个数留了 $j$ 张选票，$>v_1/k$ 的个数的最小值，直接这样暴力 DP，复杂度即为 $O(nw^2\log m)$，代码。
额，出了点小 BUG，我们发现答案的上限不应该超过 $m$，所以实际上枚举答案才是更好的选择，设 $f(i,j)$ 表示考虑前 $i$ 个数，答案为 $j$，$>v_1/k$ 数的个数的上一轮留下的 $a_{i-1}$ 的最小值，暴力 DP，复杂度即为 $O(nmw\log m)$，代码。
注意到你是枚举一个形如 $\lfloor (ax+b)/c\rfloor$ 的函数，只需要枚举到它 $\le m$ 的值，而且在 $\lfloor (ax+b)/c\rfloor$ 相同的时候应该尽量最大化 $x$，容易发现最大化的 $x'$ 满足： $$x'=\bigg\lfloor\frac{c\lfloor(ax+b)/c\rfloor+c-b-1}{a}\bigg\rfloor$$ 复杂度 $O(nm^2\log m)$，代码。
转化思路：获得更好的做法
- 由于某个奆佬想拿这个阴间思路出阴间题，所以这篇博客在写作的时候先隐藏了，如果这篇博客开放了，说明阴间题没出成，
毕竟对于极逊队来说可能还是太水了。 - upd：这题出成了，但是被一堆奆佬爆踩的了。
- 稍微提一下这个思路的发展历程：奆佬，奆佬，奆佬，菜鸡。
- 简单介绍一下这玩意的复杂度：$O(n\log^3 m)$，某个阴间人物想到的阴间数据范围是 $n\le 10^4,1\le m,a_i,v_i\le 10^9$，时间限制 $2$ 秒。
你发现问题即我们要分配 $a_i$ 以最小化： $$\sum_{i}\bigg\lfloor\frac{v_ik-1}{v_1}\bigg\rfloor=\frac1{v_1}\bigg(\sum_{i}(v_ik-1)-\sum_i(v_ik-1)\bmod v_1\bigg)$$ 然后你发现问题变成了最大化 $\sum_i(v_ik-1)\bmod v_1$，可以采用传统的动态规划算法，但这里显然有更好的做法。
你发现对于任意一种可行解，对于 $v_i,v_{i+1}$，如果我们能够调整 $a_i$ 使得 $(v_ik-1)\bmod v_1$ 更大，那么这样做必然使得整体的答案不更劣，原因是显然的：假如我们使得 $(v_ik-1)\bmod v_1$ 增加了 $\Delta$，那么我们最坏的情况也只是使得 $(v_{i+1}k-1)\bmod v_1$ 减小了 $\Delta$，但实际上，由于取模的存在，$(v_{i+1}k-1)\bmod v_1$ 不一定能减小 $\Delta$（虽然在模 $v_1$ 意义下恰好“减了”$\Delta$），而这造成了答案的增加。
你发现这个性质实际上说明了按照如下的贪心可以构造出最优解：分配 $a_2$ 使得 $(v_2k-1)\bmod v_1$ 最大，在此基础上分配 $a_3$ 使得 $(v_3k-1)\bmod v_1$ 最大……这个朴素的贪心居然是正确的！采取合适的枚举方式，问题的复杂度即为 $O(nm\log m)$，代码。
优化
我们的问题在于如何快速求解形如这样的问题： $$\max\{(ai+b)\bmod p\mid i\in[0,n]\}$$
- 其实有很简单的方法可以做到 $O(\sqrt n\log n)$，代码，复杂度 $O(n\sqrt w\log w\log n)$。
二分答案 $k$，问题转化为计数： $$\sum_{i=0}^n[(ai+b)\bmod p\le k]$$ 艾弗森括号不太好处理，但是你发现： $$[x\bmod p\le k]=\lfloor x/p\rfloor-\lfloor(x-k)/p\rfloor$$ 因此现在问题变成一个经典的类欧几里得问题，计算： $$\sum_{i=0}^n\bigg\lfloor\frac{ai+b}p\bigg\rfloor-\sum_{i=0}^n\bigg\lfloor\frac{ai+b-k}p\bigg\rfloor$$ 因此我们就得到了此题 $O(n\log^3m)$ 的算法，你可以在这题看到类似的套路，代码。
再优化
- 目前的复杂度为 $O(n\log m\log n)$，原因是前面那个式子可以 $\log m$ 求，方法如下，代码。
- 最后真正出出来的数据范围是：$n\le 10^5$，$m,a_i,v_i\le 10^9$。
如果不考虑类欧的问题，这个技巧其实在我们将枚举的 $O(w)$ 变成 $O(m)$ 的时候已经实现了，这其实算是一种简单拓展吧（然而你猜白糖怎么想到的？照着类欧的式子瞎推推出来的，因此在实际过程中困难了许多，还是推荐这个翻转上下然后利用单调性压缩的思想理解）。
花絮
在正解是 $O(n\log^3m)$ 算法的时候，我们曾经采取过多种方法卡常，主要是外层二分算上下界可以减半常数（随机数据下 $\log$ 可以消掉，不过我们针对它进行了数据的加强），内层二分适当使用插值查找也可以加速。
有两个做法在纯随机大数据下几乎必然正确，一个是 $O(n)$ 算法，代码，一个是 $O(n\log m)$ 算法，代码。
其中后一种做法较为难卡，为了卡掉后一种做法（以及它可能的随机化以及数据范围分治版本）……我们差点放弃……不过最后找到了一种足够强度的随机方式能稳定卡它，但是它对小数据不起效果，对于小数据我们是专门对着撞的。
另外，我的代码被某位大佬 hack了，具体原因是在累计变量中爆了长整型，已经修改，作者为自己代码在如此重要的场合对大家可能进行的误导深表歉意。
在本次集训队互测中，一共有两人场切了此题，一人似乎被卡常了（可惜了，虽然本人实现的代码并没有经过任何的常数实现优化）（似乎还有几位奆佬不屑于做此题 QwQ），请允许我向他们致以敬意。
同样对哪些在场上的跟正解类似但又不尽相同的做法感兴趣，若我真能抽出时间，或许会讲一讲好的做法吧。
