本文共 1651 字,大约阅读时间需要 5 分钟。
原链:[](https://blog.csdn.net/destiny1507/article/details/81751168?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522159788511519724839249788%2522%252C%2522scm%2522%253A%252220140713.130102334…%2522%257D&request_id=159788511519724839249788&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2allfirst_rank_ecpm_v3~pc_rank_v2-2-81751168.first_rank_ecpm_v3_pc_rank_v2&utm_term=%E4%B8%AD%E5%9B%BD%E5%89%A9%E4%BD%99%E5%AE%9A%E7%90%86+%E7%AE%97%E6%B3%95&spm=1018.2118.3001.4187)
①如果a%b=c,那么如果x%b=c/2,此时x=a/2;也就是说除数相等时,被除数和余数是成比例的。
②如果a%b=c,那么 (a + k*b)%b=c,其中k为整数
问题引入:
在《孙子算经》中有这样一个问题:“今有物不知其数,三三数之剩二(除以3余2),五五数之剩三(除以5余3),七七数之剩二(除以7余2),问物几何?”这个问题称为“孙子问题”,该问题的一般解法国际上称为“中国剩余定理”。
具体解法分下面三步:
1、找出三个数:从3和5的公倍数中找出被7除余1的最小数15,从3和7的公倍数中找出被5除余1 的最小数21,最后从5和7的公倍数中找出除3余1的最小数70。
2、用15乘以2(2为最终结果除以7的余数),用21乘以3(3为最终结果除以5的余数),同理,用70乘以2(2为最终结果除以3的余数),然后把三个乘积相加15∗2+21∗3+70∗215∗2+21∗3+70∗2得到和233。
3、用233除以3、5、7的最小公倍数105,得到余数23,这个余数23就是符合条件的最小数。
解释:
那么我们可能会问:为什么要这样算……
如果我们设出三个数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的角度出发可以得到:
1、n1需要是5、7的倍数;
2、n2需要是3、7的倍数;
3、n3需要是3、5的倍数;
如果找到了满足上面的三个条件的n1、n2、n3,根据上面的推论,n1+n2+n3就是满足题目要求的那个数,(但不一定是最小的哈)
接下来的问题就是----------------------我们要怎么在5和7的倍数中找出一个数满足%3=2(2、3条件类似)
我们最开始列出的第一个公式还没有用呢!是不是可以转化成在5和7的倍数中找到一个数满足%3=1就可以了呢?然后我们再*2就可以了,为什么会想要让余数为1呢?因为这个跟逆元的求法几乎一样~。
必不可少的板子:
//中国剩余定理模板typedef long long ll;ll china(ll a[],ll b[],int n)//a[]为除数,b[]为余数{ ll M=1,y,x=0; for(int i=0;i
**注:*在倒数第二行的式子中,w(b[i]/t)x中,x其实是式子 wx+a[i]*y=gcd 求出来的“逆元”,打引号是因为真正的逆元式子右边应该是1而不是gcd 因此要把x/t,这是的x/t才是真正的逆元,然后我们再乘以余数b[i]*w,得到的就是我们想要的