Cheongrin 的游戏开发 (Hard)

1. 工作次数与天数

设最终的共同进度为 $T$，所需天数为 $m$。任务 $i$ 必须被选择 $c_i=(T-a_i)/b_i$ 次。以下条件是必要且充分的：

$$c_i\in\mathbb Z_{\ge0},\qquad \sum_{i=1}^N c_i=Km,\qquad \max_i c_i\le m.$$

必要性显然。对于充分性，当剩余 $m>0$ 天时，选择剩余次数最多的 $K$ 项任务。至少有 $K$ 项任务的剩余次数为正，且剩余次数等于 $m$ 的任务至多有 $K$ 项，因此这些任务都会被选中。将选中任务的次数减一后，总次数变为 $K(m-1)$，每项任务的次数至多为 。重复此操作即可构造合法安排。

2. 最终进度的范围

令 $C=10^{18}$、$H=\max_i a_i$、。进度不会减少，每项任务每天至多被选择一次，因此任何满足 的解都满足 。根据输入保证，如果此区间内不存在 的解，就应判定为无解。仅有 并不能保证 ，因此仍需单独检查天数。

3. 广义中国剩余定理

所有 $c_i$ 都是整数，等价于对每项任务都有 $T\equiv a_i\pmod{b_i}$。维护合并后的条件 ，其中 ，初始为 。将 代入下一个同余式，得到 。

令 $g=\gcd(D,b_i)$。若 $g$ 不能整除 $a_i-r$，则无解。否则，令 ，求

$$x\equiv\frac{a_i-r}{g}\left(\frac Dg\right)^{-1}\pmod q$$

在 $[0,q)$ 内的解，再更新 $r\leftarrow r+Dx$、$D\leftarrow Dq$。当 $$ 时取 。模逆元可以用扩展欧几里得算法求出。

若合并过程中出现 $D>U$，则 $[0,U]$ 内唯一可能的值是 $r$。停止合并，直接对整个输入检查 $T=r$ 的同余条件、范围、总次数、最大次数和天数上限。尚未合并的同余条件也必须检查。

4. 一次式与下界

如果所有条件合并后仍有 $D\le U$，则令 $T=r+Dt$。定义整数

$$\alpha_i=\frac{r-a_i}{b_i},\quad\beta_i=\frac D{b_i},\quad A=\sum_i\alpha_i,\quad W=\sum_i\beta_i.$$

于是 $c_i=\alpha_i+\beta_i t$，。由于 ，天数随 增大而增大。先令 。

将 $c_i\le m$ 整理为 $(K\beta_i-W)t\le A-K\alpha_i$。当 时，可得下界

$$t\ge\left\lceil\frac{K\alpha_i-A}{W-K\beta_i}\right\rceil.$$

用这些下界更新 $\ell$。其余任务留到最后检查候选解时处理。必须正确实现分子为负数时的向上取整除法。

5. 第一个满足同余条件的候选值

总次数必须是 $K$ 的倍数，因此求解 $Wt\equiv-A\pmod K$。令 $g=\gcd(W,K)$。若 不能整除 ，则无解。否则将两边除以 ，利用模逆元得到 ，其中 ，。当 时取 。不小于下界的第一个候选值为

$$t_*=t_0+P\left\lceil\frac{\ell-t_0}{P}\right\rceil.$$

先检查 $t_*\le\lfloor(U-r)/D\rfloor$。若不满足，不进行大数乘法，直接判定无解。否则计算 $T=r+Dt_*$，并直接检查全部原始条件。

6. 为什么只需检查一个候选值

所有满足 $K\beta_i<W$ 的条件都已计入下界。对于其余任务，$(K\beta_i-W)t$ 不会减小，因此第一个候选值若违反不等式，后续候选值也都会违反。天数 同样递增，所以第一个候选值若满足 ，后面的候选值也不可能有效。因此，第一个候选值成功时就是最优解，失败时则无解。

7. 整数范围与复杂度

有 $U\le10^{27}+10^9$。由于仅在 $D\le U$ 时继续合并，新周期满足 $$。与模逆元相乘前应先取模。一次式的总和及下界计算的分子，其绝对值可安全地限制在 以内。先确认候选值的范围，再将它与 相乘，并由 重新计算工作次数和天数。因此，该实现中的所有中间值都能存入有符号 位整数。不能无限制地计算完整最小公倍数，也不能直接将超出范围的候选值与 相乘。

令 $B=\max_i b_i$，在固定宽度整数运算下，时间复杂度为 $O(N\log B+\log K)$，空间复杂度为 。

8. 子任务解法

子任务 1 中，$b_i=1$。令 $d_i=H-a_i$、、，可得 和 。当 时，只有初始进度全部相等的情况有解。否则求出下界，再枚举 在模 意义下的余数 到 ，时间复杂度为 。

子任务 2 中，枚举从 $H$ 到 $100\,000$ 的最终进度，检查必要充分条件。由于 $D\le\operatorname{lcm}(1,2,3,4,5)=60$、 且 ，上述第一个候选值满足 ，可行的最小进度小于 。因此枚举范围足够，时间复杂度为 。子任务 3 使用完整解法。

Solution written by GPT