Линейные диофантовы уравнения ax + by = c: когда есть решение и как найти все?

Уравнение ax + by = c имеет целочисленные решения тогда и только тогда, когда c делится на g = gcd(a, b). Это критерий из расширенного Евклида.

Алгоритм:

1. Найди g = gcd(a,b) и коэффициенты x0, y0: a·x0 + b·y0 = g (расширенный Евклид).
2. Если c % g != 0 → решений нет.
3. Иначе домножь на c/g: одно частное решение x = x0·(c/g), y = y0·(c/g).

Общее решение (все целые решения):

x = x0·(c/g) + k·(b/g)
y = y0·(c/g) − k·(a/g)

для любого целого k.

bool solve_dio(long long a, long long b, long long c,
               long long &x, long long &y, long long &g) {
    long long x0, y0;
    g = ext_gcd(abs(a), abs(b), x0, y0);
    if (c % g != 0) return false;
    x = x0 * (c / g);
    y = y0 * (c / g);
    if (a < 0) x = -x;
    if (b < 0) y = -y;
    return true;
}

Сложность — O(log min(a,b)). Чтобы найти, например, минимальное неотрицательное x, сдвигай k: шаг по x равен b/g, поэтому x = ((x % (b/g)) + (b/g)) % (b/g) даёт наименьший неотрицательный x, а соответствующий y пересчитывается. Будь аккуратен со знаками a, b.