[問題] 演算法問題

[cutekid (可愛小孩子)]

n 個相異正整數: n1,n2,n3 ...

一正整數 r: n1,n2,n3 ... 除以 r 的餘數都不相等

試求 r 最小是多少

請問這題除了令 r = 2,3,4 ... 一直遞增試除下去以外

有什麼好的算法嗎

謝謝 ^_^

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.221.80.36
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1465796763.A.3A7.html
推 springman: r 應該可以從 n 開始試吧！
對喔，可以從 n 開始試
推 springman: r 最大是不是這 n 個數字的最大值 - 最小值 + 1 呢？
※ 編輯: cutekid (61.221.80.36), 06/13/2016 15:28:34
推 springman: r 顯然不能與任兩個數字的差相等，只是好像沒用。
推 LPH66: 也不能是這些差的因數; 把這些數全部搜集起來之後
→ LPH66: 求最小不在其中的數應該就是答案了
→ LPH66: 另外 r 有可能會是全部的最大值; 例如輸入是前 n 個自然數
→ LPH66: 噢, 仔細想了一下, Max-Min+1 好像是對的
→ cutekid: 謝謝 s 跟 L 大，提供 2 個減少搜尋的 heuristic
→ bigpigbigpig: Google「中國剩餘定理」「大衍求一術」
※ 編輯: cutekid (210.61.233.210), 06/28/2016 13:09:12
推 LPH66: 樓上推文好像搞錯問題了, 這題不是給定餘數...