考虑类似树剖的过程，摁换根 dp 就行了。
注意到对于任意 ，最多有 个人入住。所以只要快速找到所有要入住的人就行了，这个就容易了。
首先 ，否则可以同时除以 ，若 不与 互质则无解，否则存在逆元可以除掉。
将 分解为 ，使得 且 极大。那么有 ，否则会导致 ；于是 ，所以只需要保证 ，由于 ，不妨解出 。
考虑如何分析复杂度：一次除法 的复杂度是 的，这东西的总复杂度可以分析为平方的。
设当前 ，那么所有 都可以被买得起（直到 ，如果发生这个问题不大，因为已经除二了）；设所有 的数的前缀和为 ，那么一个 能被买得起当且仅当 ，直接线段树上二分就行。依次对每个 做，总复杂度 。
的贡献为：
也就只和前面的最小值有关，前面的最小值越小则贡献越大。那么肯定要让 之前的最小值尽可能大， 之前的最小值尽可能小。
一个想法是 降序排在前面， 升序排在后面。但是这是错的，因为其实完全可以把 的一个最大值安排为 ，然后 的贡献都大大降低了！ 是一个非常特别的量！那么 可能是什么呢？
其实这个答案是可以直接写成关于 的函数的形式的，考察两个函数的性质，可以得到：
设 表示上一步在 ，再上一步在 的 函数。
扫描 ，考虑求出所有的 的连续段。设 ，那么 的变化次数也只会和连续段数同阶。所以不放在一个对 的数据结构上去求 的连续段。
考虑证明连续段的总数：因为凸性，所以这张 的深度只有 ，通过归纳法证明出所有的 也是 级别的。
直接容斥所有 的位置，那么 的 这些连续段，是最一个基本的单位，所以直接算出段内的生成函数，并 就行了。
摁 bitset，分成 块，维护两两块构成的区间的或；散块可以暴力。这样空间需要 个 bit，存不下，解决方案是用 ST 表来预处理！遇到需要快速查询任意区间的可并信息的时候，应该首选 ST 表！
另一个做法：对于区间个数大于根号，暴力扫描即可。
对于区间个数小于根号，考虑每个出现次数大于根号的数，这个是容易的。不会做了。