「杂题记录」「NOI 2018」屠龙勇士
小 D 最近在网上发现了一款小游戏。游戏的规则如下：
- 游戏的目标是按照编号 \(1 \rightarrow n\) 顺序杀掉 \(n\) 条巨龙，每条巨龙拥有一个初始的生命值 \(a_i\) 。同时每条巨龙拥有恢复能力，当其使用恢复能力时，它的生命值就会每次增加 \(p_i\) ，直至生命值非负。只有在攻击结束后且当生命值 恰好 为 \(0\) 时它才会死去。
- 游戏开始时玩家拥有 \(m\) 把攻击力已知的剑，每次面对巨龙时，玩家只能选择一把剑，当杀死巨龙后这把剑就会消失，但作为奖励，玩家会获得全新的一把剑。
小 D 觉得这款游戏十分无聊，但最快通关的玩家可以获得 ION2018 的参赛资格，于是小 D 决定写一个笨笨的机器人帮她通关这款游戏，她写的机器人遵循以下规则：
- 每次面对巨龙时，机器人会选择当前拥有的，攻击力不高于巨龙初始生命值中攻击力最大的一把剑作为武器。如果没有这样的剑，则选择 攻击力最低 的一把剑作为武器。
- 机器人面对每条巨龙，它都会使用上一步中选择的剑攻击巨龙固定的 \(x\) 次，使巨龙的生命值减少 \(x \times ATK\) 。
- 之后，巨龙会不断使用恢复能力，每次恢复 \(p_i\) 生命值。若在使用恢复能力前或某一次恢复后其生命值为 \(0\) ，则巨龙死亡，玩家通过本关。
那么显然机器人的攻击次数是决定能否最快通关这款游戏的关键。小 D 现在得知了每条巨龙的所有属性，她想考考你，你知道应该将机器人的攻击次数 \(x\) 设置为多少，才能用最少的攻击次数通关游戏吗？
当然如果无论设置成多少都无法通关游戏，输出 \(-1\).
| 测试点编号 | \(n\) | \(m\) | \(p_i\) | \(a_i\) | 攻击力 | 其他限制 |
|---|---|---|---|---|---|---|
| 1 | \(\le 10^5\) | \(=1\) | \(=1\) | \(\le 10^5\) | \(=1\) | 无 |
| 2 | \(\le 10^5\) | \(=1\) | \(=1\) | \(\le 10^5\) | \(=1\) | 无 |
| 3 | \(\le 10^5\) | \(=1\) | \(=1\) | \(\le 10^5\) | \(\le 10^5\) | 无 |
| 4 | \(\le 10^5\) | \(=1\) | \(=1\) | \(\le 10^5\) | \(\le 10^5\) | 无 |
| 5 | \(\le 10^3\) | \(\le 10^3\) | \(\le 10^5\) | \(\le 10^5\) | \(\le 10^5\) | 特性 1、特性 2 |
| 6 | \(\le 10^3\) | \(\le 10^3\) | \(\le 10^5\) | \(\le 10^5\) | \(\le 10^5\) | 特性 1、特性 2 |
| 7 | \(\le 10^3\) | \(\le 10^3\) | \(\le 10^5\) | \(\le 10^5\) | \(\le 10^5\) | 特性 1、特性 2 |
| 8 | \(=1\) | \(=1\) | \(\le 10^8\) | \(\le 10^8\) | \(\le 10^6\) | 特性 1 |
| 9 | \(=1\) | \(=1\) | \(\le 10^8\) | \(\le 10^8\) | \(\le 10^6\) | 特性 1 |
| 10 | \(=1\) | \(=1\) | \(\le 10^8\) | \(\le 10^8\) | \(\le 10^6\) | 特性 1 |
| 11 | \(=1\) | \(=1\) | \(\le 10^8\) | \(\le 10^8\) | \(\le 10^6\) | 特性 1 |
| 12 | \(=1\) | \(=1\) | \(\le 10^8\) | \(\le 10^8\) | \(\le 10^6\) | 特性 1 |
| 13 | \(=1\) | \(=1\) | \(\le 10^8\) | \(\le 10^8\) | \(\le 10^6\) | 特性 1 |
| 14 | \(=10^5\) | \(=10^5\) | \(=1\) | \(\le 10^8\) | \(\le 10^6\) | 无特殊限制 |
| 15 | \(=10^5\) | \(=10^5\) | \(=1\) | \(\le 10^8\) | \(\le 10^6\) | 无特殊限制 |
| 16 | \(\le 10^5\) | \(\le 10^5\) | 所有 \(p_i\) 是质数 | \(\le 10^{12}\) | \(\le 10^6\) | 特性 1 |
| 17 | \(\le 10^5\) | \(\le 10^5\) | 所有 \(p_i\) 是质数 | \(\le 10^{12}\) | \(\le 10^6\) | 特性 1 |
| 18 | \(\le 10^5\) | \(\le 10^5\) | 无特殊限制 | \(\le 10^{12}\) | \(\le 10^6\) | 特性 1 |
| 19 | \(\le 10^5\) | \(\le 10^5\) | 无特殊限制 | \(\le 10^{12}\) | \(\le 10^6\) | 特性 1 |
| 20 | \(\le 10^5\) | \(\le 10^5\) | 无特殊限制 | \(\le 10^{12}\) | \(\le 10^6\) | 特性 1 |
特性 1 是指：对于任意的 \(i\)，\(a_i \le p_i\)。
特性 2 是指：\(\operatorname{lcm}(p_i) \le 10^6\)，即所有 \(p_i\) 的 最小公倍数 不大于 \(10^6\)。
对于所有的测试点，\(T \le 5\)，所有武器的攻击力 \(\le 10^6\)，所有 \(p_i\) 的最小公倍数 \(\le 10^{12}\)。
保证 $ T, n, m $ 均为正整数。
分析
易知这可以直接转化为 exCRT 问题。
主要记录一下不定方程的获取所有解问题。
不定方程形如： \[ ax+by=c \] 其中 \(x, y\) 为未知数， \(a, b\) 为常数。
裴蜀定理 指出：以上方程有整数解的充要条件为 \((a, b)|c\)。
扩展欧几里得 可以解出形如： \[ ax+by=(a, b) \] 不定方程的一组整数解。
考虑构造以下式子： \[ a\left(x+\frac{b}{(a, b)}\right)+b\left(y-\frac{a}{(a, b)}\right)=(a, b) \] 不难发现如果令： \(x' = x+\frac{b}{(a, b)}, y'=y-\frac{a}{(a, b)}\)，这样构造出来的所有解 \(x', y'\) 都能成为不定方程的一组解，可以证明这样的构造方式的调整系数是最小的，能够取到所有解。（个人喜欢把 \(\frac{*}{(a, b)}\) 称为调整系数）
考虑到上面的 扩展欧几里得 解出的方程常数项等于 \((a, b)\)，而不是 \(c\) ，考虑将解和 \((a, b)\) 一同乘 \(\frac{c}{(a, b)}\) 即可。
需要注意，乘完 \(\frac{c}{(a, b)}\) 后，调整系数 不变。
关于题目，也没有题解里面说的那么卡…注意一下数据范围里面 \(P_i = 1\) 的情况即可。
关于代码，换了一种 exCRT 的写法，应该会好背很多，。