题单链接 ZR 2026 Summer C 7.29

中国剩余定理（CRT）/ 曹冲养猪 (洛谷-P1495)

CRT 模版题。顺便复习一下我的 CRT

中国剩余定理（Chinese Remainder Theorem, CRT），用于求解如下形式的一元线性同余方程组：

我们计算所有模数的积 $n$ ，对于第 $i$ 个方程，求出 $p_i=\frac{n}{m_i}$ 以及$p_i$ 在 $\text{mod } m_i$ 意义下的逆元 $p_i^{-1}$。

最后方程组的唯一解为 $x=\sum p_ip_i^{-1}a_i\ (\text{mod }n)$ 。证明略~

扩展中国剩余定理（EXCRT） (洛谷-P4777)

相比较 CRT 而言， exCRT 处理更一般的情况，即模数不两两互质的情况。不过与 CRT 几乎无关，而是使用 exGCD 合并方程组来求解的。

设已经合并了的方程为 $x\equiv A(\text{mod }M)$ ，合并到了 $x\equiv a_i(\text{mod }m_i)$ 这个方程。

转化为 $x=Ay_1+ M=a_iy_2+m_i$ ，移项 $Ay_1-a_iy_2=m_i-M$ 。发现是一个标准的不定方程，直接使用裴蜀定理判断是否有解，并且使用 exGCD 求 $y_!,y_2$ 。

合并之后的方程为 $x\equiv Ay_1+M(\text{mod }\text{lcm}(m_1,m_2))$ 。继续合并下去至只剩一个即可。

屠龙勇士 (洛谷-P4774)

首先容易发现，每条龙对应的剑是固定的。可以使用平衡树维护（当然也可以用 multiset 草过去）。考虑我们求到了第 $i$ 条龙对应的剑伤害为 $q_i$ 。

随后我们转换题面，实际上是要我们求：

系数什么的不重要！先假设我们合并到第 $i$ 个方程，并且前 $i-1$ 个方程的最小解为 $r$ ，记 $M=\text{lcm}(p_1,p_2,\cdots,p_i)$ ，则通解为 $r+Mx$。

那么我们实际上就是求 $q_i(r+Mx)\equiv a_i(\text{mod }p_i)$ 的 $x$ 的最小解。移项得到 $q_iMx\equiv a_i-q_ir (\text{mod }p_i)$ 。

即不定方程：$q_iMx+p_iy=a_i-q_ir$ 。exGCD求解即可。