→算法之韩信点兵，中国剩余定理（孙子定理） |
||
| 作者:红尘随笔 | 回复/访问: 0/4854 | 发文时间:2020/11/29 16:02:45 |
| 红尘随笔 作者 2020/11/29 16:02:45 | 算法之韩信点兵，中国剩余定理（孙子定理） 在《孙子算经》中有这样一个问题：“今有物不知其数，三三数之剩二（除以3余2），五五数之剩三（除以5余3），七七数之剩二（除以7余2），问物几何？”这个问题称为“孙子问题”，该问题的一般解法国际上称为“中国剩余定理”。 解法： 第一步，找出三个数：从3和5的公倍数中找出被7除余1的最小数15，从3和7的公倍数中找出被5除余1 的最小数21，最后从5和7的公倍数中找出除3余1的最小数70 ； 第二步，用15乘以2（2为最终结果除以7的余数），用21乘以3（3为最终结果除以5的余数），同理，用70乘以2（2为最终结果除以3的余数），然后把三个乘积相加15∗2+21∗3+70∗215∗2+21∗3+70∗2得到和233 ； 第三步，用233除以3、5、7的最小公倍数105，得到余数23，这个余数23就是符合条件的最小数。 为什么要这样算… 首先引入两个数学公式： ①如果a%b=c，那么如果x%b=c/2，此时x=a/2；也就是说除数相等时，被除数和余数是成比例的。 ②如果a%b=c，那么 (a + k*b)%b=c，其中k为整数。 如果我们设出三个数n1、n2、n3，满足：n1%3=2、n2%5=3、n3%7=2； 先从n1这个角度出发，能不能让n1+n2也满足%3=2呢？根据上面的公式②，如果n2是3的倍数就完全可以满足，同样如果让n1+n2+n3满足%3=2，需要n2和n3都是3的倍数； 同样的，我们从n2和n3的角度出发可以得到： n1需要是5、7的倍数； n2需要是3、7的倍数； n3需要是3、5的倍数； 如果找到了满足上面的三个条件的n1、n2、n3，根据上面的推论，n1+n2+n3就是满足要求的那个数，（但不一定是最小的） 接下来的就是在5和7的倍数中找出一个数满足%3=2（2、3条件类似） 根据列出的第一个公式，可以转化成在5和7的倍数中找到一个数满足%3=1，然后我们再*2就可以了。为什么会想要让余数为1呢？因为这个跟逆元的求法几乎一样。 求逆元的方法： ①费马小定理 假如p是质数，且gcd(a,p)=1，那么 a(p-1)≡1（mod p）。即：假如a是整数，p是质数，且a,p互质(即两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1。 ②扩展欧几里得 |