求两数倍数和为定值及满足A*x+B*y=C(x,y≥1)的高效算法

嘿，这两个问题本质上都是线性丢番图方程的实际应用，咱们直接跳过暴力枚举的笨办法，聊聊高效的数论解法：

问题1：如何找到两个数的倍数，使其和为特定数值 #

先明确问题：给定两个正整数 a、b，以及目标和 S，我们要找正整数 x、y，满足 a*x + b*y = S（默认倍数至少是1倍，要是允许0倍的话后面可以微调）。

第一步：快速判断是否存在解 #

别上来就找解，先筛掉不可能的情况：

• 计算 g = gcd(a, b)（两个数的最大公约数），如果 S 不能被 g 整除，直接无解——因为左边 a*x + b*y 必然是 g 的倍数，右边不是的话等式不可能成立。
• 另外，如果 S < a + b，也直接无解——毕竟x、y至少是1，最小的和就是a*1 + b*1。

第二步：用数论方法快速找解 #

如果通过了可行性判断，咱们把方程简化后用扩展欧几里得算法搞定：

1. 简化方程：把 a、b、S 都除以 g，得到 a'*x + b'*y = S'，此时 a' 和 b' 是互质的（最大公约数为1），问题变简单了。
2. 找特解：用扩展欧几里得算法找到一组整数解 (x0, y0) 满足 a'*x0 + b'*y0 = 1，然后两边乘 S'，就得到原简化方程的一组特解：x特 = x0*S'，y特 = y0*S'。
3. 生成通解：简化方程的所有整数解可以表示为：

   x = x特 + k*b'
   y = y特 - k*a'
   

   这里 k 是任意整数。
4. 筛选正整数解：解不等式组找合法的 k：
   • x特 + k*b' ≥ 1
   • y特 - k*a' ≥ 1
     只要这个不等式组有整数解 k，代入就能得到一组符合要求的 x、y。

举个实际例子：a=2，b=3，S=11。g=1，S≥5，可行。扩展欧几里得找到 2*(-1) + 3*1 =1，特解是 x=-11，y=11。通解是 x=-11+3k，y=11-2k。解不等式得 k≥4 且 k≤5，取k=4得x=1,y=3，取k=5得x=4,y=1，都是有效解。

问题2：给定A、B、C，找x,y≥1的整数解的更优算法 #

上面的方法已经是最优解了，比暴力枚举高效N倍，尤其是当A、B、C很大的时候。这里再补充几个关键优化点，让解法更快更稳：

核心优化流程 #

1. 提前过滤无解情况：
   • 先算 g = gcd(A,B)，如果 C % g != 0，直接返回无解。
   • 如果 C < A + B，也直接返回无解（x、y至少为1，最小和是A+B）。
   • 简化方程到互质形式：A'=A/g，B'=B/g，C'=C/g，此时A'和B'互质，问题简化为找A'x + B'y = C'的正整数解。
2. 快速求解特解：
   扩展欧几里得算法的时间复杂度是 O(log(min(A,B)))，哪怕A、B是1e9级别的数，也能瞬间算出特解，完全不用遍历。
3. 精准定位k的范围：
   不用挨个试k，直接计算合法k的边界：

   k_min = ceil( (1 - x特) / B' )
   k_max = floor( (y特 - 1) / A' )
   

   如果 k_min ≤ k_max，说明存在解，随便取这个范围内的整数k代入通解公式，就能得到一组有效解。

避坑小贴士 #

• 特解可能是负数，计算k的时候别搞反不等式的方向。
• 如果允许x或y为0，只需要把不等式改成≥0，调整k的范围就行。
• 当A或B是1的时候，可以直接口算解：比如A=1，那么x = C - B*y，只要y≥1且C - B*y≥1，取y在1 ≤ y ≤ (C-1)/B之间的整数就行，不用走完整流程。

和暴力枚举的对比 #

比如A=1e9，B=1e9，C=1e18，暴力枚举x从1到C/A根本不可能，但用这个方法，瞬间就能判断g=1e9，C是g的倍数，且C≥A+B，然后简化方程到x + y = 1e9，随便取x=1,y=999999999就行，效率差了几个数量级。

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