c - 在c中用2个未知参数求解方程的最快算法？

Question

我正在计算 x 和 y 的可能组合的值。它有效，但是当我输入大数字时，它花费的时间太长了。您对更好的算法有什么想法吗？

ax + by = c

程序的输入是a、b、c，必须是非负数。我的代码如下所示:

int combs=0;
for(int x=0; x < c; x++) {
    for(int y=0; y < c; y++) {
        if( (a*x) + (b*y) == c) {
            combs++;
        }
    }
}

Answer 1

一个更快的方法是先做一些数学运算。 ax+by=c => y=(c-ax)/b

int combs=0;
for(int x=0; x < c; x++) {
    int y = (c-a*x)/b;
    if( (a*x) + (b*y) == c)
        combs++;
}

摆脱嵌套循环是提高性能的最重要细节。您可以做的另一件事是按照 Antti Haapala 在下面的评论中建议的那样做，并使用 ax 而不是 x。

int combs=0;
for(int ax=0; ax < c; ax+=a) {
    int y = (c-ax)/b;
    if( (ax) + (b*y) == c)
        combs++;
}