作者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/cn.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