就写下中国剩余定理好了，其实包括扩展都可以用屠龙勇士那道题的方法写式子推，\(n\log n\) 就出来了，只是中国剩余定理的做法比较巧，所以写一下。

---

题目：

给出多个类似 \(x\equiv b_i\pmod {a_i}\) 的式子，保证 \(a\) 之间两两互质，求 \(x\)

做法：

设 \(M=\operatorname{lcm}(a_1,a_2,\cdots,a_n)\)

再设 \(k_i=\dfrac{M}{a_i}\)，并找到 \(p_i\) 使得 \(p_i\cdot k_i\equiv1\pmod{a_i}\)

那么 \(ans=p_1\cdot k_1\cdot b_1+p_2\cdot k_2\cdot b_2+\cdots+p_n\cdot k_n\cdot b_n\)

对于第 \(i\) 个同余式，除了第 \(i\) 项之外的 \(k_i\) 都包含 \(a_i\) 所以不会产生贡献。

\(p_i\cdot k_i\equiv1\pmod{a_i}\)

\(p_i\cdot k_i\cdot b_i\equiv b_i\pmod{a_i}\)

---

其实中国剩余定理本质上是个构造。