中国剩余定理：

x ≡ a1 (% m1)

x ≡ a2 (% m2)

.

.

.

x ≡ an (% mn)

m1,m2...mn 互质。

我们求里面的x，就会用到中国剩余定理。

首先将 x 看成 s ，则

s ≡ a1 (% m1) 1式

s + m1 * y = a1

另 M = m1 * m2 * m3 * m4 * ... * mn

Mi = M / mi

因为 m1,m2...mn 互质

所以 (Mi, mi) = 1

所以 可以表示成 Mi * x + mi * y = 1 2式

所以 Mi * x = 1 (% mi)

也就是说 x 为 mi 下 Mi 的逆

将 2式 扩大 a1 倍得到 Mi * x * a1 + mi * y * a1 = 1; 3式

因为 y * a1 是 % mi 的次数 ，可以写成 y

所以 3式 <=> Mi * x * a1 + mi * y = 1;

观察 1式 与 3式 得

s = Mi * xi * a1 (xi 为 Mi 在%mi 意义下的逆元)

由于有n个式子，那么

S=∑ai * Mi *xi（其中x为Mi逆元，求逆元我们可以用之前学的扩展欧几里得）

将结果mod M，得到最小解