algorithm - 找出一个数字是否是其他数字的倍数之和的算法

Question

我有三个数字 6,9,20。对于给定的数字，我需要检查它是否可以等于这三个数字的倍数之和。例如：n = 47 那么可以确定 47 = 9*3 + 20

n=23 那么不可能没有组合。

它可以在 o(n^3) 中确定。但是有没有更好的方法呢？

Answer 1

这是一个线性丢番图方程。

如果系数可以为负，则检查Bézout 的恒等式：

如果总和是数字的 gcd 的倍数，那么就有一个解决方案。

在您的示例gcd = 1中，因此有任何总和的解决方案。所以我猜你正在寻找非负系数.. :(

Answer 2

我想我有一个适合你的解决方案（仅当系数可以为 0 时）。

6和9的倍数之和都是3的倍数（除了3本身）。所以我们可以说，我们需要检查一个数字是否等于3*k + 20*l。

所以，如果你有一个号码n，

• 如果n是 3 的倍数，有一个分解，我们可以发现它很简单（如果n是偶数，它是x*6，如果它是奇数，它是9+x*6
• 如果n不是 3 的倍数，则减少 20 直到达到，然后转到第一步。如果你低于 0 并且仍然没有找到 3 的倍数，那么就没有解决方案。
• 至少有一个解决方案n > 60

小心 23 和 43，因为 3 不能这样写，23 和 43 也不能。

为什么要这样做？因为20 mod 3 = 2, 40 mod 3 = 1, 60 mod 3 =0. 所以最多减 20 2 次后，你会发现一个 3 的倍数很容易解。