用 c 语言求解2个未知参数方程的最快算法？

Question

I am counting the value of possible combinations of x and y. It works but when I put big numbers it takes way too long. Do you have any ideas for better algorithm?

ax + by = c

The input of program is a, b and c, which should be non-negative numbers. My code looks like this:

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

转载于:https://stackoverflow.com/questions/53250060/the-fastest-algorithm-to-solve-equation-with-2-unknown-parametrs-in-c

Answer 1

A much faster way is to do some math first. 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++;
}

Getting rid of that nested loop is the most important detail to improve performance. Another thing you could do is to do as Antti Haapala suggested in comments below and use ax instead of x.

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