P4774 [NOI2018] 屠龙勇士
P4774 屠龙勇士题目描述
小 D 最近在网上发现了一款小游戏。游戏的规则如下：
[*]游戏的目标是按照编号 \(1 \rightarrow n\) 顺序杀掉 \(n\) 条巨龙，每条巨龙拥有一个初始的生命值 \(a_i\) 。同时每条巨龙拥有恢复能力，当其使用恢复能力时，它的生命值就会每次增加 \(p_i\) ，直至生命值非负。只有在攻击结束后且当生命值 恰好 为 \(0\) 时它才会死去。
[*]游戏开始时玩家拥有 \(m\) 把攻击力已知的剑，每次面对巨龙时，玩家只能选择一把剑，当杀死巨龙后这把剑就会消失，但作为奖励，玩家会获得全新的一把剑。
小 D 觉得这款游戏十分无聊，但最快通关的玩家可以获得 ION2018 的参赛资格，于是小 D 决定写一个笨笨的机器人帮她通关这款游戏，她写的机器人遵循以下规则：
[*]每次面对巨龙时，机器人会选择当前拥有的，攻击力不高于巨龙初始生命值中攻击力最大的一把剑作为武器。如果没有这样的剑，则选择 攻击力最低 的一把剑作为武器。
[*]机器人面对每条巨龙，它都会使用上一步中选择的剑攻击巨龙固定的 \(x\) 次，使巨龙的生命值减少 \(x \times ATK\) 。
[*]之后，巨龙会不断使用恢复能力，每次恢复 \(p_i\) 生命值。若在使用恢复能力前或某一次恢复后其生命值为 \(0\) ，则巨龙死亡，玩家通过本关。
那么显然机器人的攻击次数是决定能否最快通关这款游戏的关键。小 D 现在得知了每条巨龙的所有属性，她想考考你，你知道应该将机器人的攻击次数 \(x\) 设置为多少，才能用最少的攻击次数通关游戏吗？
当然如果无论设置成多少都无法通关游戏，输出 \(-1\) 即可。
数据范围
对于所有的测试点，\(T \le 5\)，所有武器的攻击力 \(\le 10^6\)，所有 \(p_i\) 的最小公倍数 \(\le 10^{12}\)。
保证 $ T, n, m $ 均为正整数。
solution:
我们不难发现其实砍每条龙的剑是唯一确定的，根据题意，我们恰好砍死一条龙时的伤害方程为：
\
其中 \(atk\) 表示砍的次数，\(K\) 表示回了多少次血。
转化一下：
\
我们假设用来砍这条龙的剑伤为 \(b_i\) （即上述式子中的 \(x\) ）,那么我们就要求一个 最小攻击次数 \(x\) 满足：
\
我们先思考一下在 excrt 中我们是这么处理的：
假设之前 \(i-1\) 个方程合并出了一个解 \(ans\) 和一个所有 \(p\) 的 最小公倍数 \(lcm\)。那么前 \(i-1\) 个方程的通解可表示为 ：\(ans+x\times lcm\)
我们要让这个通解满足现在的方程：
\
然后我们将同余方程转成等式：
\
移项：
\[(b_i\times lcm)x+(-p_i)y = a_i -b_i\times ans\]
看到这个式子就说明这题写完了，直接 exgcd 求解就完了。
但是还要注意一些细节：首先是选剑，我们可以用平衡树或者 multiset 实现。还有就是我们求出来的答案要把龙砍死，所以要注意一下最难砍的那条龙最少要砍几刀，如果答案不到那个数，记得加回去。
都是做 crt 的人了，__int128这种常识就不需要多说了吧~~
Code:
#include#define ll __int128const int N=1e5+5;using namespace std;ll read(){ ll res=0;char c=getchar(); while(c
页:
[1]