Python实现的中国剩余定理算法示例
本文实例讲述了Python实现的中国剩余定理算法。分享给大家供大家参考，具体如下：
中国剩余定理（ChineseRemainderTheorem-CRT）:又称孙子定理，是数论中的一个定理。即如果一个人知道了一个数n被多个整数相除得到的余数，当这些除数两两互质的情况下，这个人就可以唯一的确定被这些个整数乘积除n所得的余数。
维基百科上wiki：TheChineseremaindertheoremisatheoremofnumbertheory,whichstatesthat,ifoneknowstheremaindersofthedivisionofanintegernbyseveralintegers,thenonecandetermineuniquelytheremainderofthedivisionofnbytheproductoftheseintegers,undertheconditionthatthedivisorsarepairwisecoprime.
有一数n，被2除余1，被3除余2，被5除余4，被6除余5，正好被7整除，求该数n.
分析：n被2除余1，说明概述最小为1，之后该条件一直满足，所以需要加上的数一定是2的倍数。被3除余2，即（1+2*i）%3=2，其中i为正整数。之后该条件一直满足，所以需要加上的数一定是3的倍数，又因为前一个条件的限制，所以是2和3的最小公倍数的整数倍。一次类推，知道找到被7整除的数。
n=1 while(n%3!=2): n+=2 while(n%5!=4): n+=6 while(n%6!=5): n+=30 while(n%7!=0): n+=30
最终结果为119。
更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》
希望本文所述对大家Python程序设计有所帮助。