如何找到满足双数倍数与GCD约束的最小数值？求无循环解法

问题描述 #

给定两个整数x、y，需找到最小正整数val，满足：

1. val是max(x,y)的倍数；
2. (val - gcd(x,y)) 或 (val + gcd(x,y)) 是min(x,y)的倍数。

公式表示为：

val % max(x,y) == 0 and ((val - gcd(x,y)) % min(x,y) == 0 or (val + gcd(x,y)) % min(x,y) == 0)

示例：输入4和7时，val=7。因为7是max(4,7)=7的倍数，且7+gcd(4,7)=8是min(4,7)=4的倍数。

现有解法的问题 #

当前通过循环递增val（每次加max(x,y)）的方式，在x、y数值较大时，循环次数可能极多，导致运行效率低下。代码如下：

from math import gcd
x,y=map(int,input().split())
def fun(x,y):
    big=max(x,y)
    small=min(x,y)
    d=gcd(x,y)
    val=big
    while (val+d)%small!=0 and (val-d)%small!=0:
        val+=big
    return val
val=fun(x,y)
print(val)

数学推导与高效解法 #

通过数学变换可彻底避免循环，直接计算最小val：

变量替换与条件转化 #

设：

• big = max(x,y)，small = min(x,y)
• d = gcd(x,y)
• 提取最大公约数后，令big = d * B，small = d * S，此时gcd(B,S)=1（已无公共因子）

因为val是big的倍数，设val = k * big = k*d*B（k为正整数），代入条件2：

1. (val - d) % small == 0 → 化简得 kB ≡ 1 mod S
2. (val + d) % small == 0 → 化简得 kB ≡ -1 mod S

我们需要找到最小的正整数k，满足上述两个同余式之一，对应的val = k*big即为答案。

核心计算逻辑 #

由于gcd(B,S)=1，B在模S下存在逆元：

• 计算inv_B：B的逆元模S，即满足B*inv_B ≡1 mod S的最小正整数
• k1 = inv_B % S（对应kB ≡1 mod S的最小k）
• k2 = (-inv_B) % S（对应kB ≡-1 mod S的最小k）

取k1和k2中的较小值，乘以big即可得到最小val。

实现代码 #

from math import gcd

def extended_gcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = extended_gcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    # 扩展欧几里得算法求a在模m下的逆元，前提是gcd(a,m)=1
    g, x, _ = extended_gcd(a, m)
    return x % m

def find_min_val(x, y):
    big = max(x, y)
    small = min(x, y)
    d = gcd(x, y)
    B = big // d
    S = small // d
    
    inv_B = modinv(B, S)
    k1 = inv_B % S
    k2 = (-inv_B) % S
    
    min_k = min(k1, k2)
    return min_k * big

x, y = map(int, input().split())
print(find_min_val(x, y))

示例验证 #

输入4和7：

• d = gcd(4,7)=1
• B=7//1=7，S=4//1=4
• inv_B是7在模4下的逆元：7≡3 mod4，3*3=9≡1 mod4，故inv_B=3
• k1=3，k2=(-3)%4=1
• min_k=1，val=1*7=7，符合示例结果。

复杂度分析 #

该解法依赖扩展欧几里得算法求逆元，时间复杂度为O(log(max(B,S)))，远优于循环解法的线性复杂度，可高效处理大数输入。

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