警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

「算法」CRT - 数论

简介

CRT 可以在 \(b_1\cdots b_k\) 两两互质时,解出形如

\[ \left\{\begin{array}{ccc} x & \equiv & a_1\pmod{b_1} \\ x & \equiv & a_2\pmod{b_2} \\ & \vdots \\ x & \equiv & a_k\pmod{b_k} \end{array}\right. \]

的方程组。

流程

令:

  • \(m=\prod_{i=1}^nb_i\)\(\operatorname{lcm}(b_1,\cdots,b_n)\)
  • \(m_i\)\(\frac m{b_i}\)
  • \(t_i\)\(m_i\) 在模 \(b_i\) 意义下的逆元

那么有 \(x=\sum_{i=1}^na_im_it_i\)

证明:

\[ \begin{aligned} & x \\ \equiv & \sum_{j=1}^na_jm_jt_j\pmod{b_i} \\ \equiv & a_im_it_i + \sum_{j\ne i}^na_jm_jt_j\pmod{b_i} \\ \equiv & a_i + 0\pmod{b_i} \\ \equiv & a_i\pmod{b_i} \\ \end{aligned} \]

第三行到第四行是因为 \(\forall_{j\ne i}, b_i\mid m_j \Rightarrow m_j\equiv0\pmod b_i\)

exCRT

\(b_1,\cdots,b_n\) 不两两互质时,普通 CRT 就用不了了。

假设我们已知前 \(k-1\) 个方程的方程组的通解为 \(x+t\cdot\operatorname{lcm}_{i=1}^{k-1}b_i\)

那么将其作为未知数代入第 \(k\) 个方程,即 \(x + t\cdot\operatorname{lcm}_{i=1}^{k-1}b_i\equiv a_k\pmod{b_k}\)

移项得 \(t\cdot\operatorname{lcm}_{i=1}^{k-1}b_i\equiv a_k-x\pmod{b_k}\)\(t\cdot\operatorname{lcm}_{i=1}^{k-1}b_i-y\cdot b_k=a_k-x\)

所以只要用 exgcd 求解就好了。

解出来 \(t\) 就可以得到前 \(k\) 个方程的方程组的一个解为 \(x+t\cdot\operatorname{lcm}_{i=1}^{k-1}b_i\),然后又可以推出通解,继续迭代即可。

所以还要 CRT 干什么?

代码

CRT

传送门:洛谷 P3868 - 猜数字

exCRT

传送门:洛谷 P4777 - 扩展中国剩余定理(EXCRT)