作者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