在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++;
}