引入
我国古代数学著作《孙子算经》中有一道题目，它的描述是这样的
今有物不知其数，三三数之余二；五五数之余三；七七数之余二。问物几何？
这道题用现代数学理论来看，无非就是解一个方程
begin{cases}xequiv 2left( mod 3right) \
xequiv 3left( mod 5right) \
xequiv 2left( mod 7right) end{cases}
那么这个方程怎么解呢？
这需要用到我们祖先的伟大创造——中国剩余定理
中国剩余定理
在很久以前，数学领域还没有像扩展欧几里得这种东西。对于这个问题，我们祖先采用了构造的方法
构造过程如下
首先考虑三个特殊方程
begin{cases}xequiv 1left( mod 3right) \
xequiv 0left( mod 5right) \
xequiv 0left( mod 7right) end{cases}
begin{cases}xequiv 0left( mod 3right) \
xequiv 1left( mod 5right) \
xequiv 0left( mod 7right) end{cases}
begin{cases}xequiv 0left( mod 3right) \
xequiv 0left( mod 5right) \
xequiv 1left( mod 7right) end{cases}
他们的特殊解
那第一个方程来说，它实际上等同于解一个同余式
$$35yequiv 1left( mod 3right) $$
因为$x$一定是$5*7=35$的倍数
化简一下当面的式子
$$2yequiv 1left( mod 3right) $$
我们不难得出解$y=2$，此时$x=70$
同理，对于第二第三个式子我们可以运用相同的方法求解
$$begin{pmatrix} 1 \ 0 \ 0 end{pmatrix}=70begin{pmatrix} 0 \ 1 \ 0 end{pmatrix}=21begin{pmatrix} 0 \ 0 \ 1 end{pmatrix}=15$$
那么最终的答案为
$$begin{pmatrix} 2 \ 3 \ 2 end{pmatrix}=2begin{pmatrix} 1 \ 0 \ 0 end{pmatrix}+3begin{pmatrix} 0 \ 1 \ 0 end{pmatrix}+2begin{pmatrix} 0 \ 0 \ 1 end{pmatrix}$$
$$=2times 70+3times 21+2times 15equiv 23left( mod 105right)$$
我们这样就可以求出解了。
但是这仅仅是三个式子的情况，如果推广到$r$个呢?
其实是一样的，都是利用构造的手段。
下面我们来推广一下。
设有$r$个同余式，其中$m_i$两两互素，注意$m$必须两两互素，否则答案错误。其实不互素也可以搞不过要用更神奇的东西
设$N=prod ^{r}_{i=1}m_{i}$
对于同余方程组
$$begin{cases}xequiv b_{1}left( mod m_{1}right) \ xequiv b_{2}left( mod m_{2}right) \ ldots \ xequiv brleft( mod m_rright) end{cases}$$
在模$N$同余的意义下有唯一解
这个方程怎么解呢？
我们仍然像前面一样，考虑构造
$$begin{cases}xequiv 0left( mod m_{1}right) \ ldots \ xequiv 0left( mod m_{i-1}right) \ ldots \ xequiv 1left( mod m_{i}right) \ ldots \ xequiv 0left( mod m_{i+1}right) \ ldots \ xequiv0left( mod M_{r}right) end{cases}$$
像上面那样，我们令$x=(N/m_i)*y$
那么我们现在需要解出
$left( N/m_{i}right) yequiv 1left( mod m_{i}right) $
这个东西怎么搞呢？
聪明的你肯定已经知道啦，这不就是个逆元嘛，想怎么搞就怎么搞
如果你不知道怎么搞的话可以看这里
那么方程的解为$x_{0}=b_{1}x_{1}+b_{2}x_{2}+ldots +b_{r}x_{r}left( mod Nright)$
怎么样？似不似很简单？
例题
有了上面的知识代码应该不难写
放一道水题
http://poj.org/problem?id=1006
题解（很久之前做的）
- 还没有人评论，欢迎说说您的想法！
客服
