c - 如何在C中找到所有可能的选项？

Question

我正在尝试在 C 语言中找到一种有效的算法，它为我提供给定方程的所有选项。

我有方程 AX + BY = M，其中 A、B 和 M 我通过输入 (scanf) 获得。

For example lets have: 5X + 10Y = 45

• 第一个选项:5 * 9 + 10 * 0
• 第二个选项:5 * 7 + 10 * 1
• 第n个选项:5 * 1 +10*4

而且我还需要计算存在多少种可能的选项？一些技巧、提示？

我忘了说 X 和 Y 在 Z 中并且 >= 0，所以没有无限的选择。

Answer 1

如果您限制非负未知数，这个问题就有意义。

将方程重写为

AX = M - BY.

只要 RHS 为正，就可以有正解，即

BY ≤ M,

或

Y ≤ M/B.

那么对于给定的 Y，存在一个解 iff

A|(M - BY)

您可以在 Python 中将其编码为

for Y in range(M / B + 1):
    if (M - B * Y) % A == 0:
        X= (M - B * Y) / A

解决办法是

9 0
7 1
5 2
3 3
1 4

迭代次数等于M/B。如果A > B，最好交换X和Y。