标签 - 中国剩余定理

? 解题记录 ? ? UOJ ? ? 中国剩余定理 ? ? 扩展欧几里得 ?    2018-09-16 09:39:49    432    0    0
http://uoj.ac/problem/396 一、一些小处理 首先,每一条龙该使用哪一把剑是严格确定的,这个可以用set加lower_bound预处理出来。我们发现,要想打死一条龙,需要满足的条件是: $$ atk_ix\equiv hp_i(mod\ p_i) 且 atk_ix \geq hp_i $$ 其中$atk_i$是预处理出的攻击力,$hp_i$是巨龙的血量,$p_i$是恢复能力。 对于后面的限制是好做的,只要求出前面同余方程组的解就可以解出满足后面性质的最小解。 对于前面形如$ax\equiv c(mod\ p) $的方程,我们用扩展欧几里得对$x$求解