问题：给定正整数\(m_1, m_2, ... , m_n\) 和 \(a_1, a_2, ... , a_n\) 求关于 x 的同余方程组的一个解：

\[\left\{ \begin{aligned} x \equiv a_1 \pmod {m_1} \\ x \equiv a_2 \pmod {m_2}\\ \vdots \qquad \qquad \quad \quad \\ x \equiv a_n \pmod {m_n} \end{aligned} \right. \]

其中，\(m_1, m_2, ..., m_n\) 两两互质。

令 \(m = \prod_{i = 1}^n m_i\) , \(M_i = \frac{m}{m_i}\)，\(t_i\) 为 \(M_i\) 在模 \(m_i\) 下的逆元，即：\(M_i \cdot t_i \equiv 1 \pmod{m_i}\)
则 x 的一个解为：

\[\begin{aligned} x = \sum_{i = 1}^n a_i M_i t_i \end{aligned} \]

方程的通解为 ： \(X = x + k\cdot m \quad (k \in Z)\)

证明：
因为\(M_i = \frac{m}{m_i}\)，\(M_i\) 是除 \(m_i\) 以外所有模数的倍数，所以总是存在：

\[\begin{aligned} a_i\cdot M_i \cdot t_i \equiv 0 \pmod{m_j} \quad (j \ne i) \\ a_i \cdot M_i \cdot t_i \equiv a_i \pmod{m_i} \quad \qquad \end{aligned} \]

所以将所有 \(a_iM_it_i\) 累加起来，就可以满足方程组中的所有方程

实现：一个for循环，用exgcd求逆元。
以下代码中，a[i] 相当于\(m_i\) b[i] 相当于

int exgcd(lld a, lld b, lld &x, lld &y) {
	if(b == 0) {
		x = 1, y = 0; return a;
	}
	int g = exgcd(b, a % b, x, y);
	lld p = x; x = y; y = p - a / b * y;
	return g;
}
void crt() {
	lld mi, ti, y;
	for(int i = 1; i <= n; i++) {
		mi = m / a[i];
		exgcd(mi, a[i], ti, y);
		ans = (ans + (b[i] * mi * ti) % m + m) % m;
	}
}