1. Идея

Нужно найти любые целые x и y, для которых выполняется уравнение

a * x + b * y = c.

Это классическая задача на линейное диофантово уравнение. Основной инструмент здесь — расширенный алгоритм Евклида.

Он позволяет для чисел a и b найти такие коэффициенты x0 и y0, что

a * x0 + b * y0 = gcd(a, b).

Тогда, если c делится на gcd(a, b), можно просто умножить это равенство на c / gcd(a, b) и получить решение для c.

Если же c не делится на gcd(a, b), решения не существует.

2. Наблюдения

Наблюдение 1. Когда решение существует

Для уравнения

a * x + b * y = c

решение в целых числах существует тогда и только тогда, когда c делится на gcd(a, b).

Это стандартный факт про линейные диофантовы уравнения.

Наблюдение 2. Что делать, если один коэффициент равен нулю

Отдельно удобно обработать случаи:

• если a == 0, то уравнение превращается в b * y = c;
• если b == 0, то уравнение превращается в a * x = c.

Тогда решение либо находится простым делением, либо не существует.

Это не только упрощает код, но и помогает аккуратно избежать лишних частных случаев в основном алгоритме.

Наблюдение 3. Расширенный алгоритм Евклида удобнее запускать на неотрицательных числах

В эталонном решении расширенный алгоритм Евклида вызывается для abs(a) и abs(b).

То есть сначала находим коэффициенты для

abs(a) * x0 + abs(b) * y0 = gcd(abs(a), abs(b)).

После этого достаточно исправить знаки:

• если a < 0, то заменить x0 на -x0;
• если b < 0, то заменить y0 на -y0.

Так мы получим коэффициенты уже для исходных a и b.

3. Алгоритм

1. Считать a, b, c.
2. Если a == 0:
   • если c не делится на b, вывести -1;
   • иначе вывести 0 и c / b.
3. Если b == 0:
   • если c не делится на a, вывести -1;
   • иначе вывести c / a и 0.
4. Иначе:
   • взять aa = abs(a) и bb = abs(b);
   • с помощью расширенного алгоритма Евклида найти x0, y0 и g, такие что
     aa * x0 + bb * y0 = g, где g = gcd(aa, bb);
   • если c % g != 0, вывести -1;
   • иначе:
     • если a < 0, поменять знак x0;
     • если b < 0, поменять знак y0;
     • положить k = c / g;
     • ответ: x = x0 * k, y = y0 * k.
5. Вывести найденные x и y.

4. Почему это работает

Пусть оба числа a и b не равны нулю.

Сначала расширенный алгоритм Евклида для aa = abs(a) и bb = abs(b) находит такие x0 и y0, что

aa * x0 + bb * y0 = g,

где g = gcd(aa, bb).

Так как gcd(abs(a), abs(b)) = gcd(a, b) по модулю знака, это именно тот наибольший общий делитель, который нужен.

Теперь восстановим знаки исходных коэффициентов:

• если a < 0, то заменим x0 на -x0;
• если b < 0, то заменим y0 на -y0.

После этого получится равенство

a * x0 + b * y0 = g.

Теперь рассмотрим число c.

Если c не делится на g

Любая сумма вида a * x + b * y всегда делится на g, потому что и a, и b делятся на g. Значит, число c, не делящееся на g, получить нельзя. Поэтому ответа нет.

Если c делится на g

Тогда существует число k = c / g, и можно умножить равенство

a * x0 + b * y0 = g

на k. Получим:

a * (x0 * k) + b * (y0 * k) = c.

Значит, x = x0 * k и y = y0 * k — корректное решение.

Почему отдельные случаи a == 0 и b == 0 тоже правильные

• При a == 0 уравнение становится b * y = c.
  Если c не делится на b, решений нет. Иначе y = c / b, а x можно взять равным 0.
• При b == 0 аналогично: a * x = c, значит либо решения нет, либо x = c / a, y = 0.

Следовательно, алгоритм всегда либо находит корректную пару, либо правильно сообщает, что решения не существует.

5. Сложность

Расширенный алгоритм Евклида работает за O(log(min(|a|, |b|))).

Итоговая сложность:

• время: O(log(min(|a|, |b|)));
• память: O(1).

6. Код на C++17

#include <iostream>
#include <cstdlib>

using namespace std;

long long extended_gcd_nonneg(long long a, long long b, long long &x, long long &y) {
    long long old_r = a, r = b;
    long long old_x = 1, x1 = 0;
    long long old_y = 0, y1 = 1;

    while (r != 0) {
        long long q = old_r / r;

        long long nr = old_r - q * r;
        old_r = r;
        r = nr;

        long long nx = old_x - q * x1;
        old_x = x1;
        x1 = nx;

        long long ny = old_y - q * y1;
        old_y = y1;
        y1 = ny;
    }

    x = old_x;
    y = old_y;
    return old_r;
}

int main() {
    long long a, b, c;
    cin >> a >> b >> c;

    if (a == 0) {
        if (c % b != 0) {
            cout << -1 << '\n';
        } else {
            cout << 0 << ' ' << c / b << '\n';
        }
        return 0;
    }

    if (b == 0) {
        if (c % a != 0) {
            cout << -1 << '\n';
        } else {
            cout << c / a << ' ' << 0 << '\n';
        }
        return 0;
    }

    long long aa = llabs(a);
    long long bb = llabs(b);

    long long x0, y0;
    long long g = extended_gcd_nonneg(aa, bb, x0, y0);

    if (c % g != 0) {
        cout << -1 << '\n';
        return 0;
    }

    if (a < 0) x0 = -x0;
    if (b < 0) y0 = -y0;

    long long k = c / g;
    long long x = x0 * k;
    long long y = y0 * k;

    cout << x << ' ' << y << '\n';
    return 0;
}

7. Код на Python 3

a, b, c = map(int, input().split())

if a == 0:
    if c % b != 0:
        print(-1)
    else:
        print(0, c // b)
elif b == 0:
    if c % a != 0:
        print(-1)
    else:
        print(c // a, 0)
else:
    aa = abs(a)
    bb = abs(b)

    old_r, r = aa, bb
    old_x, x1 = 1, 0
    old_y, y1 = 0, 1

    while r != 0:
        q = old_r // r

        old_r, r = r, old_r - q * r
        old_x, x1 = x1, old_x - q * x1
        old_y, y1 = y1, old_y - q * y1

    g = old_r
    x0 = old_x
    y0 = old_y

    if c % g != 0:
        print(-1)
    else:
        if a < 0:
            x0 = -x0
        if b < 0:
            y0 = -y0

        k = c // g
        x = x0 * k
        y = y0 * k
        print(x, y)