使用Python实现已知两数凑目标值的高效编码方案

这个问题本质是求解二元一次不定方程的非负整数解，我们可以通过数学简化+有限枚举的方式实现最高效的计算：

步骤分析 #

1. 方程简化：原方程 1500x + 1000y = 4000 两边除以两数的最大公约数500，得到等价的简化方程 3x + 2y = 8，大幅降低计算量。
2. 确定枚举范围：x是非负整数，因此x的可能取值为0到 8//3=2（仅3个可能值），遍历这个极小范围即可快速找到解。

高效实现代码 #

import math

def find_valid_counts(a=1500, b=1000, target=4000):
    # 先判断是否存在解：目标值需能被两数的最大公约数整除
    gcd = math.gcd(a, b)
    if target % gcd != 0:
        return []
    
    # 简化系数与目标值，缩小计算规模
    a_simple = a // gcd
    b_simple = b // gcd
    target_simple = target // gcd
    
    solutions = []
    # 遍历所有可能的x值，计算对应的y是否为非负整数
    max_x = target_simple // a_simple
    for x in range(max_x + 1):
        remaining = target_simple - a_simple * x
        if remaining % b_simple == 0:
            y = remaining // b_simple
            solutions.append((x, y))
    
    return solutions

# 调用示例
print(find_valid_counts())  # 输出 [(0, 4), (2, 1)]

效率说明 #

• 时间复杂度O(1)：x的枚举范围由简化后的方程决定，这里最多仅需循环3次，完全没有冗余计算。
• 提前终止无效计算：通过最大公约数先判断是否存在解，避免后续无用操作。
• 数值简化：将大整数转为小整数计算，减少运算开销。

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