CRT/ExCRT

CRT用于求解类似$$\left\{\begin{aligned}&x \equiv a_1 \pmod{m_1} \\&x \equiv a_2 \pmod{m_2} \\&… \\&x \equiv a_n \pmod{m_n}\end{aligned}\right.$$其中，$\forall i, j, ~ (m_i, m_j) = 1$ 设 $M = \prod_{i = 1}^n m_i, ~ M_i = \frac{M}{m_i}$，再设 $M_it_i \equiv 1 \pmod{m_i}$，其中 $1 \le i \le n$ 则可构造一解 $x = \sum\limits_{i = 1}^n a_iM_it_i$，任意解 $x_0 = x + k \times M$ ExCRT用于求解类似$$\left\{\begin{aligned}&x \equiv a_1 \pmod{m_1} \\&x \equiv a_2 \pmod{m_2} \\&… \\&x \equiv a_n \pmod{m_n}\e ...