Разбор задачи «Закупка двух типов товаров»

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

a * x + b * y = c

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

Если решений нет, нужно вывести -1.

1. Идея

Это задача на линейное диофантово уравнение.

Сначала нужно понять, существует ли вообще целочисленное решение уравнения

a * x + b * y = c.

Известный факт: оно существует тогда и только тогда, когда gcd(a, b) делит c.

Но нам недостаточно просто любого решения. Нужно найти решение с:

• x >= 0
• y >= 0
• x минимально

Эталонное решение делает это очень удобно:

1. С помощью расширенного алгоритма Евклида находит коэффициенты для a и b.
2. Строит из них обратный элемент и получает минимальное неотрицательное значение x, удовлетворяющее сравнению.
3. По найденному x вычисляет y.
4. Проверяет, что y >= 0.

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

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

Пусть g = gcd(a, b).

Тогда уравнение

a * x + b * y = c

имеет целочисленное решение только если c % g == 0.

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

Наблюдение 2. Переход к сокращённому уравнению

Если g делит c, разделим всё на g:

• a1 = a / g
• b1 = b / g
• c1 = c / g

Тогда получаем уравнение

a1 * x + b1 * y = c1

Причём gcd(a1, b1) = 1.

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

Из уравнения

a1 * x + b1 * y = c1

получаем сравнение по модулю b1:

a1 * x ≡ c1 mod b1

Так как a1 и b1 взаимно просты, у числа a1 существует обратный элемент по модулю b1.

Если найти число inv, для которого

a1 * inv ≡ 1 mod b1,

то

x ≡ c1 * inv mod b1.

Значит, минимальное неотрицательное решение по x — это просто остаток

x = (c1 * inv) mod b1.

Именно это значение даёт наименьший возможный x среди всех целых решений, подходящих по сравнению.

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

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

y = (c - a * x) / b

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

Почему? Потому что все остальные решения имеют вид

• x увеличивается на b1
• y уменьшается на a1

То есть если уже для минимального x значение y отрицательно, то при больших x оно станет только меньше.

3. Алгоритм

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

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

Расширенный алгоритм Евклида возвращает числа px и py, для которых

a * px + b * py = g.

После деления на g получаем, что px — это обратный элемент для a1 по модулю b1, потому что

a1 * px + b1 * py = 1.

Значит,

a1 * px ≡ 1 mod b1.

То есть inv = px mod b1 действительно является обратным элементом.

Теперь из сравнения

a1 * x ≡ c1 mod b1

получаем

x ≡ c1 * inv mod b1.

Все решения этого сравнения имеют вид

x = x0 + k * b1.

Минимальное неотрицательное среди них — это как раз остаток

x0 = (c1 * inv) mod b1.

Далее по исходному уравнению находим

y = (c - a * x) / b.

Это число целое, потому что x выбрано так, что сравнение выполнено.

Остаётся проверить неотрицательность:

• если y >= 0, найдено корректное решение;
• если y < 0, то любое другое решение будет иметь ещё больший x и ещё меньший y, значит неотрицательных решений не существует.

Следовательно, алгоритм либо находит пару (x, y) с минимальным x, либо правильно сообщает, что решения нет.

5. Сложность

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

Все остальные действия выполняются за O(1).

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

• время: O(log min(a, b))
• память: O(log min(a, b)) из-за рекурсии

6. Код на C++17

#include <iostream>
using namespace std;

long long extended_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 = extended_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 = extended_gcd(a, b, xg, yg);

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

    long long a1 = a / g;
    long long b1 = b / g;
    long long c1 = c / g;

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

    long long x = (__int128)(c1 % b1) * inv % b1;
    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 extended_gcd(x, y):
    if y == 0:
        return x, 1, 0
    g, x1, y1 = extended_gcd(y, x % y)
    return g, y1, x1 - (x // y) * y1

g, px, py = extended_gcd(a, b)

if c % g != 0:
    print(-1)
else:
    a1 = a // g
    b1 = b // g
    c1 = c // g

    inv = px % b1
    x = (c1 % b1) * inv % b1
    y = (c - a * x) // b

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