首页 > 代码库 > 【中国剩余定理】-从简到难

【中国剩余定理】-从简到难

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

【中国剩余定理】-从简到难