CRT

一句话理解

CRT 中国剩余定理：模数两两互质时方程组有唯一模 M 解。

为什么要学

拆模。

讲解

x≡a_i (mod m_i)。构造 sum a_i M_i inv_i。

例子

韩信点兵。

常见错误

• 模不互质还用朴素 CRT。
• 乘法溢出。