作者cutekid (可愛小孩子)
看板Prob_Solve
標題[問題] 演算法問題
時間Mon Jun 13 13:46:00 2016
n 個相異正整數: n1,n2,n3 ...
一正整數 r: n1,n2,n3 ... 除以 r 的餘數都不相等
試求 r 最小是多少
請問這題除了令 r = 2,3,4 ... 一直遞增試除下去以外
有什麼好的算法嗎
謝謝 ^_^
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.221.80.36
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1465796763.A.3A7.html
1F：推 springman: r 應該可以從 n 開始試吧！ 06/13 13:58
對喔，可以從 n 開始試
2F：推 springman: r 最大是不是這 n 個數字的最大值 - 最小值 + 1 呢？ 06/13 14:03
※ 編輯: cutekid (61.221.80.36), 06/13/2016 15:28:34
3F：推 springman: r 顯然不能與任兩個數字的差相等，只是好像沒用。 06/13 16:07
4F：推 LPH66: 也不能是這些差的因數; 把這些數全部搜集起來之後 06/13 21:52
5F：→ LPH66: 求最小不在其中的數應該就是答案了 06/13 21:52
6F：→ LPH66: 另外 r 有可能會是全部的最大值; 例如輸入是前 n 個自然數 06/13 21:54
7F：→ LPH66: 噢, 仔細想了一下, Max-Min+1 好像是對的 06/13 21:55
8F：→ cutekid: 謝謝 s 跟 L 大，提供 2 個減少搜尋的 heuristic 06/14 12:21
9F：→ bigpigbigpig: Google「中國剩餘定理」「大衍求一術」 06/28 00:14
※ 編輯: cutekid (210.61.233.210), 06/28/2016 13:09:12
10F：推 LPH66: 樓上推文好像搞錯問題了, 這題不是給定餘數... 06/28 17:34