当前位置: 代码迷 >> 综合 >> 韩信点兵(中国剩余定理)
  详细解决方案

韩信点兵(中国剩余定理)

热度:66   发布时间:2023-12-26 00:55:53.0

孙子算经中有记载:“今有数不知其数:二三数之余而,五五之数余三,七七数之余而,问物几何?”它的意思就是有一些物品,如果3个3个数
剩两个,如果5个5个数,最后剩3个,如果7个个7个数,最后剩2个,求这些物品的数量,这个问题称为孙子问题,西方数学家称为中国剩余定理
方法就是除3的余数a乘上70,除5的余数b乘上21,除7的余数c乘上15,最后再取余105
70,21,15实际上是一种巧妙的构造方法。
70是5和7的公约数,且被3除余1
21是3和7的公约数,且被5除余1
15是3和5的公约数,且被7除余1
这样结果这个数等于=70a+21b+15c就能保证被被3除余a,且被5除余b,且被7除余c
比如,求除以5、7、11以后所得余数为a,b,c.则这个数是:231a+330b+210c,然后对5×7×11=385取余即可。