Re: [問題] 離散問題

看板Grad-ProbAsk作者square690410 (阿隆)時間16年前 (2009/03/18 22:33)推噓1(1推 0噓 1→)

留言2則, 1人參與討論串2/3 (看更多)

※ 引述《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

推

wind1227

03/19 00:19, , 1^F

03/19 00:19, 1^F

→

wind1227

03/19 00:20, , 2^F

03/19 00:20, 2^F

‣ 返回看板[ Grad-ProbAsk ] 研究

‣ 更多 square690410 的文章

文章代碼(AID): #19mGOdlL (Grad-ProbAsk)