Самый быстрый алгоритм для решения уравнения с 2 неизвестными параметрами в с?

Question

Я рассчитываю значение возможных комбинаций х и у. Это работает, но когда я ставлю большие цифры, это занимает слишком много времени. У вас есть идеи по улучшению алгоритма?

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

Избавление от этого вложенного цикла является наиболее важной деталью для повышения производительности.Другая вещь, которую вы можете сделать, это сделать, как предложил Антти Хаапала в комментариях ниже, и использовать топор вместо x.

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