問題：
給定一個輸入(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 之間。
uj5u.com熱心網友回復：
如果范圍內有兩個 X 的倍數，則數字 X 可能是范圍內兩個數字的 gcd。
所以我們需要找到最大的 X 使得有 m 使得 mX >= lower_bound 并且 (m 1)X <= upper_bound。
對于給定的 m，如果 floor(upper_bound/(m 1)) * m >= lower_bound，則滿足此條件的最大 X（如果有）是 X = floor(upper_bound / (m 1))。請注意，較大的 m 將給出較小的 X，因此我們需要找到可能的最小 m 來找到最大的 X。
現在我們可以嘗試 m=1、m=2 等等，直到我們找到一個 X（這將是最大可能的 X）。
請注意，我們偷偷地避免與 gcd 有任何關系：如果我們找到最大的 X 使得范圍內有兩個 X 的倍數，那么這兩個 X 的倍數必然有 gcd X。我們可以找到最大的 X通過找到最小的 m 使得 mX 和 (m 1)X 都在范圍內（并為那個 m 選擇最大的 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 的存在不是單調的）。
uj5u.com熱心網友回復：
將使用lower和upper（洗掉_bound）和gcd作為 GCD(X, Y)。
對于較低的樓層（upper/2），gcd 接近后者。
對于接近上限的下限，上限 - 下限是上限。
from math import sqrt, ceil
def highest_GCD(lower, upper, mess=(__name__ == '__main__')):
""" Return max{ GCD(X, Y) such that lower <= X < Y <= upper }. """
# ToDo: useful test cases
if not 0 < lower < upper:
return None if not mess else None, 'No GCD for lack of numbers'
limit = ceil(sqrt(upper)) # one factor got to be smaller
gap = upper - lower
candidates = (upper // factor for factor in range(upper // gap, limit)
) if limit < gap else range(gap, 0, -1)
for candidate in candidates:
higher = upper - upper % candidate
if lower <= higher - candidate:
return candidate if not mess else (
candidate, 'highest GCD in [%d, %d] is %d, dividing X=%d, Y=%d' % (
lower, upper, candidate, higher - candidate, higher))
（使用v - v%c僅僅是替代f = v // c，f*c 保羅·漢金已經習慣了。
我不喜歡一個比其他（或引進一個floor_multiple(n, factor)單個發生。））
（This was in a company's coding round
?一個真正的PITA！或者只是如果你硬著頭皮代碼檢查質量解決方案“足夠快，直到經驗表明并非如此”您完全知道性能不滿意。）
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/408845.html
標籤：
上一篇：試圖理解阿姆達爾定律