中国剩余定理


关键字: 

·模数两两互质。

·拓展欧几里德求(a1*a2*...*a-1*x)%ak=1 的x

·找最小的要不减去 最小公倍数


  感觉古人很机智,不过中国剩余定理对于除数不互质的情况是不能够解决的哦~~要用到前面那个方法。

下面是中国剩余定理的详细过程:

最后一步成的(3*5*7)表示的是所有除数的最小公倍数。(因为他们互质嘛-.-)

in my opinion...中国剩余定理的主要思想应该是:对于一个式子,找到一个满足该式子的被除数,且该被除数能整除其他式子的除数,那么我们把那些数加起来之后便能满足所有式子了。要去最小正整数的话,就一直减他们的最小公倍数即可。

2016-02-02 10:04:16


2016-08-27 15:30:16 更新

原文地址:https://www.cnblogs.com/Konjakmoyu/p/5176848.html