作者square690410 (阿隆)
看板Grad-ProbAsk
标题Re: [问题] 离散 问题
时间Wed Mar 18 22:33:10 2009
※ 引述《yshihyu (yshihyu)》之铭言：
: X 余 2 (mod 3)
: X 余 1 (mod 4)
: X 余 2 (mod 5)
: 要找X 最小两个整数值
: 请问最小两个要怎麽找?
: 答案应该是 17, 77
: 谢谢
这个好像是今年的清大的，不过不辛的，我考的时候也熊熊 的失忆了
用中国余数定理...纯背SOP就好了....在考你记不记得而已...XD
3,4,5彼此互质，不用再拆了
n1 = 3, n2 = 4 , n3 = 5 , N = n1*n2*n3 = 3*4*5 = 60
r1 = 2, r2 = 1 , r3 = 2
N1 = 60/3 = 20 , N2 = 60/4 = 15 , N3 = 60/5 = 12
M1 = N1 mod n1的inverse = 2, M2 = N2 mod n2 的inverse = 3
M3 = N3 mod n3的inverse = 3
(例inverse就是求 N1*? (mod n1 ) = 1，求那个?，如 20x mod 3 = 1，
取x = 2 ，2*20 = 40, 40 mod 3 = 1，所以inverse为2)
取X = r1M1N1 + r2M2N2 + r3M3N3 = 2*2*20 + 1*3*15 + 2*3*12 = 80+45+72
= 197 (mod N=60) = 17 , 最小整数...
17 + 60 = 77 (第二小的整数)
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 59.124.113.121
1F：推 wind1227:考台科前才看的结果没考...一个礼拜後清大就考了... 03/19 00:19
2F：→ wind1227:可是也忘了... 03/19 00:20