学术：浅谈中国剩余定理

中国剩余定理，古中国人发现的关于一元线性同余方程组的定理，形式化表达如下：

目标是求解 的最小解。显然的，会有多解情形 。

希望读了这份讲解之后能够觉得自己也能发现这个巧妙的定理。

对于每一个方程，我们都可以写作：

的形式。

根据加法同余，我们希望能够把解写成如下的形式：

这个时候考虑 是一个自然不过的选择。

但是我们发现，这样子项与项之间是会影响的， 的话就会影响方程 的成立，怎么办？我们希望给 套个壳，让他对于所有 的情况都无视化。这个时候我们基于取模的性质，想到如果 这样就好了，可以抵消其他地方的影响了：

一个容易的考虑就是 ，这样取模之后为 ，在加法同余下就不会有任何影响了。但是不好的消息是，现在对于方程 又有影响了，所以再在外面套一层 即可。

注意我们写作 而不是 其实是有智慧的。看似无用，实则该模则模该过则过。这个也算是 的妙用、无中生有的巅峰了！

所以整体的思路和代码其实异常简单：

1. 求出模数之积 ；
2. 对于每个方程：

• 求出 ；
• 求出 ，可能需要 ；

3. ，注意最后的取模保证最小解；

以下是模板代码：

for (int i = 1; i <= n; ++i) {
    LL m = tot / mod[i];
    LL inv = exgcd(m, mod[i]).first;
    inv = (inv % mod[i] + mod[i]) % mod[i];
    ans = (ans + mul(mul(m, inv, tot), a[i], tot)) % tot;
}