1. Идея

Нужно найти неотрицательные целые x и y, такие что

a * x + b * y = c

и среди всех таких решений выбрать то, у которого x минимально.

Это классическая задача на линейное диофантово уравнение. Базовый факт такой:

• решение существует тогда и только тогда, когда gcd(a, b) делит c;
• если одно решение найдено, то все остальные можно выразить через него.

Но здесь требуется не просто любое решение, а решение с минимальным x среди неотрицательных. Эталонное решение делает это очень аккуратно через сравнение по модулю.

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

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

Пусть g = gcd(a, b). Тогда уравнение

a * x + b * y = c

имеет целочисленные решения только если c делится на g.

Если c % g != 0, сразу выводим -1.

Наблюдение 2. Что даёт расширенный алгоритм Евклида

Расширенный алгоритм Евклида находит такие числа xg и yg, что

a * xg + b * yg = g

Тогда после умножения на c / g получаем одно решение уравнения для c.

Но эталонное решение использует это чуть иначе: из xg получается обратный элемент для числа a / g по модулю b / g.

Наблюдение 3. Как получить минимальный x

Разделим уравнение на g:

aa * x + bb * y = cc

где

• aa = a / g
• bb = b / g
• cc = c / g

Тогда нужно решить сравнение

aa * x ≡ cc (mod bb)

Так как gcd(aa, bb) = 1, число aa обратимо по модулю bb.

Из расширенного алгоритма Евклида мы знаем, что

a * xg + b * yg = g

После деления на g:

aa * xg + bb * yg = 1

Значит, xg — это обратный элемент к aa по модулю bb.

Тогда

x ≡ cc * xg (mod bb)

Среди всех таких x минимальное неотрицательное значение получается как остаток по модулю bb.

Именно его и вычисляет решение.

Наблюдение 4. Почему потом достаточно проверить y >= 0

После выбора минимального неотрицательного x значение y однозначно находится:

y = (c - a * x) / b

Если y < 0, то неотрицательного решения вообще нет.

Почему? Потому что все решения имеют вид x = x0 + k * bb, то есть любой другой неотрицательный x только больше или равен найденному минимальному. Тогда y будет только уменьшаться. Если уже при минимальном x значение y отрицательно, то дальше станет ещё меньше.

3. Алгоритм

1. Считать a, b, c.
2. С помощью расширенного алгоритма Евклида найти g = gcd(a, b) и коэффициенты xg, yg, для которых a * xg + b * yg = g.
3. Если c % g != 0, вывести -1.
4. Иначе вычислить:
   • aa = a / g
   • bb = b / g
   • cc = c / g
5. Найти обратный элемент к aa по модулю bb:
   • inv = xg % bb
   • если остаток отрицательный, привести его к положительному.
6. Вычислить минимальное неотрицательное x:
   • x = (cc % bb) * inv % bb
7. Вычислить
   • y = (c - a * x) / b
8. Если y < 0, вывести -1.
9. Иначе вывести x и y.

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

Докажем корректность алгоритма.

Шаг 1. Проверка существования решения

Расширенный алгоритм Евклида даёт g = gcd(a, b). Из теории линейных диофантовых уравнений известно:

• если g не делит c, решений нет;
• если g делит c, целочисленные решения существуют.

Значит, проверка c % g != 0 корректна.

Шаг 2. Получение сравнения для x

Если решение существует, делим уравнение на g:

aa * x + bb * y = cc

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

Из этого равенства следует:

aa * x ≡ cc (mod bb)

И наоборот: если x удовлетворяет этому сравнению, то cc - aa * x делится на bb, значит можно выразить целое y.

Шаг 3. Почему xg — обратный элемент

Из расширенного алгоритма:

a * xg + b * yg = g

Делим на g:

aa * xg + bb * yg = 1

Если смотреть по модулю bb, получаем:

aa * xg ≡ 1 (mod bb)

Значит, xg действительно обратен к aa по модулю bb.

Тогда решение сравнения:

x ≡ cc * xg (mod bb)

А минимальное неотрицательное решение этого сравнения — это именно

x = (cc % bb) * inv % bb

где inv = xg mod bb.

Шаг 4. Почему найденный x минимален

Все решения сравнения по модулю bb имеют вид:

x = x0 + k * bb

где x0 — наименьший неотрицательный остаток.

Алгоритм как раз находит такой x0. Значит, среди всех целых решений это минимальный неотрицательный x, который вообще может участвовать в уравнении.

Шаг 5. Почему достаточно проверить только найденный y

После нахождения x вычисляем

y = (c - a * x) / b

Это целое число, потому что x удовлетворяет нужному сравнению.

Если y >= 0, то получена подходящая пара неотрицательных чисел.

Если y < 0, рассмотрим любое другое решение. Его x будет равно x + k * bb для некоторого k >= 1, потому что найденный x уже минимален среди неотрицательных. Тогда

a * x увеличится, а значит y = (c - a * x) / b уменьшится ещё сильнее. Следовательно, неотрицательного y уже не получится ни для какого другого решения.

Значит, в этом случае ответа не существует, и вывод -1 корректен.

5. Сложность

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

Все остальные действия — константные.

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

• время: O(log(min(a, b)))
• память: O(log(min(a, b))) из-за рекурсии в расширенном алгоритме Евклида

6. Код на C++17

#include <iostream>
using namespace std;

long long ext_gcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long x1, y1;
    long long g = ext_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

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

    long long xg, yg;
    long long g = ext_gcd(a, b, xg, yg);

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

    long long aa = a / g;
    long long bb = b / g;
    long long cc = c / g;

    long long inv = xg % bb;
    if (inv < 0) inv += bb;

    long long x = (__int128)(cc % bb) * inv % bb;
    long long y = (c - a * x) / b;

    if (y < 0) {
        cout << -1 << "\n";
    } else {
        cout << x << " " << y << "\n";
    }

    return 0;
}

7. Код на Python 3

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

def ext_gcd(x, y):
    if y == 0:
        return x, 1, 0
    g, x1, y1 = ext_gcd(y, x % y)
    return g, y1, x1 - (x // y) * y1

g, xg, yg = ext_gcd(a, b)

if c % g != 0:
    print(-1)
else:
    aa = a // g
    bb = b // g
    cc = c // g

    inv = xg % bb
    x = (cc % bb) * inv % bb
    y = (c - a * x) // b

    if y < 0:
        print(-1)
    else:
        print(x, y)