algorithm - 如何找到 2 个数字的最高 GCD，使得这 2 个数字来自给定的数字范围？

Question

问题:

给定输入(lower_bound, upper_bound)，计算:

max{ GCD(X,Y), (X,Y) satisfying lower_bound <= X < Y <= upper_bound }

示例:

INPUT: lower_bound = 1, upper_bound = 100000
OUTPUT: 50000, obtained with X=50000, Y=100000

INPUT: lower_bound = 3, upper_bound = 4
OUTPUT: 1, obtained with X=3, Y=4

这是在一家公司的编码回合中，基本上寻找所有可能对的 GCD 的暴力方法不起作用。

它对示例测试用例有效，但在提交过程中对隐藏测试用例超时。

众所周知，输入的 lower_bound 和 upper_bound 将始终在 1 到 1000000 之间。

Answer 1

如果范围内有两个 X 的倍数，则数字 X 是该范围内两个数字的可能 gcd。

因此，我们需要找到最大的 X，使得有 m 个满足 mX >= lower_bound 且 (m+1)X <= upper_bound 的条件。

对于给定的m，满足此条件的最大X(如果有)是X = Floor(upper_bound/(m+1))，如果floor(upper_bound/(m+1)) * m >= lower_bound。请注意，较大的 m 会给出较小的 X，因此我们需要找到尽可能小的 m 来找到最大的 X。

现在我们可以尝试 m=1、m=2 等等，直到找到 X(这将是可能的最大 X)。

请注意，我们偷偷地避免了与 gcd 相关的任何事情:如果我们找到最大的 X，使得范围内有 X 的两个倍数，那么 X 的这两个倍数必然具有 gcd X。我们可以找到通过找到最小的 m 使得 mX 和 (m+1)X 都在该范围内(并为该 m 选择最大的 X)来最大这样的 X。

例如:

def findX(lower, upper):
    for m in range(1, lower+1):
        x = upper // (m + 1)
        if x * m >= lower:
            return 'input:%d,%d => %d, obtained with X=%d, Y=%d' % (lower, upper, x, x * m, x * (m+1))

print(findX(3, 4))
print(findX(10000, 10010))
print(findX(50000, 99999))
print(findX(50000, 100000))

输出:

input:3,4 => 1, obtained with X=3, Y=4
input:10000,10010 => 10, obtained with X=10000, Y=10010
input:50000,99999 => 33333, obtained with X=66666, Y=99999
input:50000,100000 => 50000, obtained with X=50000, Y=100000

(注意:此答案的早期编辑使用二分搜索来查找 m 和 x。这是错误的，因为特定 m 的 x 的存在不是单调的)。