如何高效求解给定数值区间内两个数的最大GCD？

Alright, let's tackle this problem efficiently—since brute-forcing all possible (X,Y) pairs is definitely not going to cut it for large ranges up to 1,000,000. Let's break down the logic and build a solution that runs in near-constant time for most cases, and at worst O(√n) time.

Problem Recap #

We need to find the maximum GCD of any pair (X,Y) where lower_bound ≤ X < Y ≤ upper_bound (let's shorthand these as L and R for simplicity). The brute-force approach of checking every pair works for small test cases but times out immediately for large ranges.

Core Insight #

The maximum possible GCD d must have at least two multiples within [L, R]. In other words, there exist integers a < b such that d*a ≥ L and d*b ≤ R. With this in mind, we can split the problem into two easy-to-handle scenarios:

Scenario 1: R ≥ 2*L #

If the upper bound is at least twice the lower bound, then R//2 is guaranteed to be ≥ L. The pair (R//2, R) will have a GCD of R//2, which is the largest possible value we can get here. Why? Because any d larger than R//2 would only have one multiple in the range (since 2d would exceed R), so we can't form a valid pair.

For example, if L=1 and R=100000, R//2=50000—the pair (50000, 100000) gives us the maximum GCD of 50000.

Scenario 2: R < 2*L #

Here, all numbers in the range are relatively close together, so we can't rely on the previous trick. Instead, the maximum GCD will be the largest divisor of R (or another large number in the range) that has at least one other multiple in [L, R-1].

Instead of checking every number from R-1 down to 1 (which could be slow for tight ranges), we can enumerate all divisors of R (in descending order) and check if there's a multiple of that divisor in [L, R-1]. The first divisor that satisfies this condition is our answer.

For example, if L=5 and R=9:

• R's divisors are 9, 3, 1.
• 9 has no multiples in [5,8], so skip.
• 3 has 6 in [5,8], so we return 3 as the maximum GCD.

Edge Cases #

• If R-L == 1 (like L=3, R=4): The pair is consecutive numbers, which are coprime—so the maximum GCD is 1.
• If L == R: There are no valid (X,Y) pairs, but per the problem statement, this input probably won't be given since X < Y is required.

Python Implementation #

import math

def max_gcd(lower_bound, upper_bound):
    L = lower_bound
    R = upper_bound
    
    # Handle edge case where no valid pairs exist
    if R <= L:
        return 0
    # Consecutive numbers are coprime
    if R - L == 1:
        return 1
    
    # Scenario 1: Upper bound is at least twice the lower bound
    if R >= 2 * L:
        return R // 2
    
    # Scenario 2: Tight range, check divisors of R
    max_d = 1
    # Enumerate all divisors of R
    for i in range(1, int(math.isqrt(R)) + 1):
        if R % i == 0:
            # Check if divisor i has a multiple in [L, R-1]
            if ( (R-1) // i - (L-1) // i ) >= 1:
                max_d = max(max_d, i)
            # Check the paired divisor (R//i)
            counterpart = R // i
            if counterpart != i:
                if ( (R-1) // counterpart - (L-1) // counterpart ) >= 1:
                    max_d = max(max_d, counterpart)
    return max_d

# Test the examples
print(max_gcd(1, 100000))  # Output: 50000
print(max_gcd(3, 4))       # Output: 1
print(max_gcd(5, 9))       # Output: 3

Why This Works #

• For Scenario 1, we get an answer in O(1) time—super fast.
• For Scenario 2, enumerating divisors takes O(√R) time, which is trivial even for R=1e6 (since √1e6=1000 iterations). Each check for multiples is done in constant time using integer division, making the whole process efficient.

内容的提问来源于stack exchange，提问作者Jack Froster