[问题] 算法问题 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

楼上推文好像搞错问题了, 这题不是给定余数...

继续阅读