数论 中国剩余定理

中国剩余定理求解如下方程：

看起来难以下手...(#｀-_ゝ-)

先设，x1%m1=a1,x2%m2=a2,...，总的答案为x

假如x1%m1=a1的同时，对于除了第一个式子以外的式子，都有x1%\(m_i\)=0,此时x+=x1，那么x%m1=a1,x%\(m_i\)=0，即x满足条件1的同时，对其余条件无任何影响

接着同样的操作，x最后就可以同时满足所有条件

假设M=\(\Pi_{i=n}^{1}m_i\)，Mi=M/mi,ti=Mi在模mi意义下的乘法逆元。Mi* ti在模mi意义下，值为1,xi=Mi* ti* ai。然后x累加所有的xi即可

中国剩余定理

原文：https://www.cnblogs.com/ticmis/p/13210797.html