中国剩余定理：
同余方程组：
\[x \equiv a_i \pmod {m_i}\,(i \in\left[1,n\right]) \]（其中 \(\forall i,j \in\left[1,n\right],\gcd(m_i,m_j) = 1\)）
有解，且这些解构成一个无穷的等差数列，公差为 \(\prod\limits_{i = 1}^{n}m_i\)。
-
有解：
设 \(M = \prod\limits_{i = 1}^{n}m_i,M_i = \frac{M}{m_i},inv_i = \frac{1}{M_i} \bmod m_i\)，
则 \(x = \sum\limits_{i = 1}^{n}a_i \times M_i \times inv_i\) 为同余方程组的一个解。
同时亦可知 \(x + k \times M (k \in \mathbb{N})\) 也是方程的一组解。
（ps：其实说到这里就能解题了）
-
公差：
设刚才考虑的一个特解为 \(x_0\)，
则对于任意一个解 \(x\) 有 \(x \equiv x_0 \pmod {m_i}\,(i \in\left[1,n\right])\)，
即 \(m_i \mid x-x_0\,(i \in \left[1,n\right])\)，
鉴于 \(m_i\) 两两互质，\(M \mid x-x_0\)。得证。
求解一组类似的同余方程组时间复杂度为 \({\mathcal{O}}(n \log M)\)
#define llt long long int
void ex_gcd(llt &a,llt b,llt &x,llt &y) {
if(!b) {
x = 1;
y = 0;
return;
}
ex_gcd(b,a%b,y,x);
y = y-a/b*x;
}
llt CRT(const int n,int *a,int *m) {
llt M = 1, Mi, x, y, res = 0;
for(int i = 1;i <= n;++i)
M *= m[i];
for(int i = 1;i <= n;++i) {
Mi = M/m[i];
ex_gcd(Mi,m[i],x,y);
res = (res+(__int128)a[i]*Mi*x)%M;
}
return (res+M)%M;
}