首页 > 代码库 > 【中国剩余定理】-从简到难
【中国剩余定理】-从简到难
1,补同缺
一个数除2余1,除3余2,除5余4,除6余5
2-1
3-2
5-4
6-5
每个都差1,给每个都补1,n+1是2,3,5,6的倍数,算得30,n+1=30,n=29
2,去同余
一个数除2余1,除3余1,除4余1,除6余1
2-1
3-1
4-1
6-1
每个都多1,给每个都去1,n-1是2,3,4,6的倍数,n-1=24,n=25
3,
a/9余0
(a+1)/8余0
(a+2)/7余0
列出来
--------------------
a a+1 a+2
9 8 7
--------------------
a+9是9的倍数
a+1+8是8的倍数
a+2+7是7的倍数
a+9是7,8,9的公倍数
就是504,a=495
如果
---------------------
a a+2 a+4
9 8 7
--------------------
下面各差一个,上面差2个,加减n轮
a+18,a+2+16,a+4+14
=a+18,是9,8,7的公倍数504.a=504-18=486
4:中国剩余定理之逐级满足法(适用任何)
5余3 7余1 9余4
先找到除5余3最小的--3
3+n //n是5的倍数,最小是0
3+n(n是5的倍数且除7余5) //n除7余5,整体3+n除7余1,得出n=5
3+5+n(n是5的倍数且是7的倍数 ,且除9余5) //n除9余5 , 8+n除9余4,得出n=175
结果是183+(579的公倍数)
//注:可以先用去同余补同缺进行优化,例:5-3,6-4,7-1 == n+2=5,6的公倍数,再求30的倍数除7余1(1是28+n除7得1,n=1),为120
结果是n+2=30,n=28,28+120=148
【中国剩余定理】-从简到难