程序员的资源宝库

网站首页 > gitee 正文

中国剩余定理。(中国剩余定理简单公式)

sanyeah 2024-04-03 18:36:29 gitee 6 ℃ 0 评论

久闻剩余定理大名,也略懂一二。。

不过今天认真学习了下。。留下此贴,以记之。
参考:http://eblog.cersp.com/userlog/7978/archives/2008/723693.shtml
http://book.51cto.com/art/200812/102579.htm

1:一个数被3除余1,被4除余2,被5除余4,这个数最小是几?
题中345三个数两两互质。
则〔45=20;〔35=15;〔34=12;〔345=60
为了使203除余1,用20×2=40
使154除余1,用15×3=45
使125除余1,用12×3=36
然后,40×145×236×4=274
因为,274>60,所以,27460×4=34,就是所求的数。

2:一个数被3除余2,被7除余4,被8除余5,这个数最小是几?
题中378三个数两两互质。
则〔78=56;〔38=24;〔37=21;〔378=168
为了使563除余1,用56×2=112
使247除余1,用24×5=120
使218除余1,用21×5=105
然后,112×2120×4105×5=1229
因为,1229>168,所以,1229168×7=53,就是所求的数。

3:一个数除以54,除以83,除以112,求满足条件的最小的自然数。
题中5811三个数两两互质。
则〔811=88;〔511=55;〔58=40;〔5811=440
为了使885除余1,用88×2=176
使558除余1,用55×7=385
使4011除余1,用40×8=320
然后,176×4385×3320×2=2499
因为,2499>440,所以,2499440×5=299,就是所求的数。

4:有一个年级的同学,每9人一排多5人,每7人一排多1人,每5人一排多2人,问这个年级至少有多少人 (幸福123老师问的题目)
题中975三个数两两互质。
则〔75=35;〔95=45;〔97=63;〔975=315
为了使359除余1,用35×8=280
使457除余1,用45×5=225
使635除余1,用63×2=126
然后,280×5225×1126×2=1877
因为,1877>315,所以,1877315×5=302,就是所求的数。

5:有一个年级的同学,每9人一排多6人,每7人一排多2人,每5人一排多3人,问这个年级至少有多少人 (泽林老师的题目)
题中975三个数两两互质。
则〔75=35;〔95=45;〔97=63;〔975=315
为了使359除余1,用35×8=280
使457除余1,用45×5=225
使635除余1,用63×2=126
然后,280×6225×2126×3=2508
因为,2508>315,所以,2508315×7=303,就是所求的数。
(例5与例4的除数相同,那么各个余数要乘的也分别相同,所不同的就是最后两步。)

 

 

先写出一个两位数62,接着在62右端写这两个数字的和为8,得到628,再写末两位数字28的和10,得到62810,用上述方法得到一个有2006位的整数:628101123……,则这个整数的数字之和是(       )。

2006-5)÷10=200....1

17+35*200+1=7018

前面的62810数字和为17

后面开始,以“1123581347”为循环节

共循环10次,每次的和为35

最后余1,就加上1

所以结果是17+35*200+1=7018


例子:PKU 1006

因为只有三个数23 28 33 且三个数两两互为质数,所以“中国剩余定理”可知
对于每一组输入数据p, e ,i, d,所求结果为:n = (R1*p + R2*e + R3*i)%21252-d
其中 R1%p=1, R2%e=1, R3%i=1;
R1 = 5544 = 28*33* 6;      //28 33 的公倍数中能被23除余1的最小整数
R2 = 14221 = 23*33*19;   //23 33 的公倍数中能被28除余1的最小整数
R3 = 1288 = 23*28* 2;      //23 28 的公倍数中能被33除余1的最小整数
       为了保证结果大于等于1且小于等于21252,结果修正为:n = (R1*p + R2*e + R3*i - d + 21252)%21252,并且如果n为0,则n = 21252为所求。

Tags:

本文暂时没有评论,来添加一个吧(●'◡'●)

欢迎 发表评论:

最近发表
标签列表