[問題] 演算法問題 cutekid PTT批踢踢實業坊

作者: cutekid (可愛小孩子) 2016-06-13 13:46:00

n 個相異正整數: n1,n2,n3 ...
一正整數 r: n1,n2,n3 ... 除以 r 的餘數都不相等
試求 r 最小是多少
請問這題除了令 r = 2,3,4 ... 一直遞增試除下去以外
有什麼好的算法嗎
謝謝 ^_^

作者: springman (司布林) 2016-06-13 13:58:00

r 應該可以從 n 開始試吧！r 最大是不是這 n 個數字的最大值 - 最小值 + 1 呢？r 顯然不能與任兩個數字的差相等，只是好像沒用。

作者: LPH66 (-6.2598534e+18f) 2016-06-13 21:52:00

也不能是這些差的因數; 把這些數全部搜集起來之後求最小不在其中的數應該就是答案了另外 r 有可能會是全部的最大值; 例如輸入是前 n 個自然數噢, 仔細想了一下, Max-Min+1 好像是對的

作者: cutekid (可愛小孩子) 2016-06-14 12:21:00

謝謝 s 跟 L 大，提供 2 個減少搜尋的 heuristic

作者: bigpigbigpig (To littlepig with love) 2016-06-28 00:14:00

Google「中國剩餘定理」「大衍求一術」

作者: LPH66 (-6.2598534e+18f) 2016-06-28 17:34:00

樓上推文好像搞錯問題了, 這題不是給定餘數...

繼續閱讀