中国剩余定理 学习笔记
问题
中国剩余定理用来解决如下问题：
求关于\(x\)的方程组
\[\begin{cases} x \equiv a_1 \pmod{p_1} \\ x \equiv a_2 \pmod{p_2} \\ \cdots \\ x \equiv a_n\pmod{p_n}\end{cases}\]
的最小非负整数解。
其中\(p_i\)两两互质。
前置技能
扩展欧几里得求乘法逆元
求解
设\(M=\prod_{i=1}^{n} p_i,d_i=\frac{M}{p_i}\)，即\(d_i\)表示除\(p_i\)外所有\(p\)的乘积。
记\(inv_i\)表示\(d_i\)在模\(p_i\)域下的逆元（因为\(p\)两两互质，所以\(d_i\)一定与\(p_i\)互质，所以一定存在逆元），即\(inv_i \times d_i \equiv 1 \pmod{p_i}\)。记\(x_i=inv_i\times d_i\)，则：
- 因为\(d_i\)能被除\(p_i\)外的所有\(p\)整除，所以\(x_i\)一定能被除\(p_i\)外的所有\(p\)整除，所以\(x_ia_i\)一定能被除\(p_i\)外的所有\(p\)整除。
- \(x_i\equiv 1 \pmod{p_i}\)，所以\(a_ix_i\equiv a_i \pmod{p_i}\)。
根据以上两条推论可得，答案为\(\left( \sum_{i=1}^{n} a_ix_i \right) \bmod M\)。因为对于第\(i\)个方程，根据推论1，对于所有的\(j\ne i\)，\(a_jx_j\)不会对该方程组产生贡献，即\(a_jx_j\equiv 0 \pmod{p_i} (j\ne i)\)。只有\(a_ix_i\)会对第\(i\)个方程产生贡献，且根据推论2，恰好会产生\(a_i\)的贡献。又因为对于所有\(i\)，\(M\equiv 0\pmod{p_i}\)，所以答案加上或减去若干个\(M\)都满足方程组。求的是最小非负整数解，所以答案\(\bmod M\)。
代码
中国剩余定理模板题：[TJOI2009]猜数字
1 |
|
