链接

先用multiset(或手写平衡树)预处理出打每条龙用的剑伤害值，记为 $B_i$

注意：题意意思是只能攻击一个来回

正题

根据题意可以写出方程：

$\left\{ \begin{aligned} &B_1x \equiv A_1 ~ (mod ~ P_1) \\ &B_2x \equiv A_2 ~ (mod ~ P_2) \\ &......... \\ &B_nx \equiv A_n ~ (mod ~ P_n) \end{aligned} \right.$

几个问题：

1. 模数P不两两互质
2. $x$ 前有系数

考虑用扩展CRT的思想转化

设在求解第 $i$ 项方程的解，已经解出前$i-1$个方程的解 $x$，记前$i-1$ 个P的最小公倍数为$m$

尽管$x$前有系数，但仍然满足$x$的通解为$x+km$

对于方程(忽略下标)

$Bx \equiv A ~ (mod ~ P)$

转化为

$B(x+km) \equiv A ~ (mod ~ P)$

展开移项

$mB \times k \equiv A-Bx ~ (mod ~ P)$

将$k$设为未知数，其实这就是一个同余方程，转化如下(x是已知)，未知数为 $k$ 和 $y$

$mB \times k + P \times y = A-Bx$

求解得到最小的$k$，则新方程的解为$x+km$

更新完$x$之后更新$m$，进行下一步求解

坑点

所以这题就做完了吗？当然没有!，NOI题怎么能这么水

1. 这题数字巨大，中途会爆long long，请使用龟速乘(或者int128)
2. $x$脱离了问题本身，如果$x$次没有把血打成负的也是不行的，所以在求解完后要使用通解式$x+km$得到不小于最大攻击次数下限中最小的解
3. 求解剑的时候用upper_bound(好像就我有这个问题)