1. Идея

Нужно найти наибольшую натуральную сумму, которую нельзя представить в виде

a * x + b * y, где x >= 0, y >= 0.

Для двух взаимно простых номиналов существует известный ответ: это число равно

a * b - a - b.

Значит, задача сводится не к перебору вариантов, а к применению этой формулы.

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

Наблюдение 1

Если a и b взаимно просты, то начиная с некоторого места все достаточно большие числа уже можно представить как

a * x + b * y.

То есть недостижимых сумм конечное число, и среди них есть наибольшая.

Наблюдение 2

Классический результат для двух взаимно простых чисел:

• наибольшее непредставимое число равно a * b - a - b.

Эту задачу часто называют задачей о монетах или задачей Фробениуса для двух чисел.

Наблюдение 3

Ограничения до 10^6 позволяют безопасно вычислить ответ в long long в C++:

• максимум a * b равен 10^12,
• это помещается в 64-битный целый тип.

3. Алгоритм

1. Считать a и b.
2. Вычислить a * b - a - b.
3. Вывести результат.

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

Покажем две ключевые вещи:

• число a * b - a - b действительно нельзя представить;
• любое число больше него уже можно представить.

Почему число a * b - a - b недостижимо

Предположим противное: существует представление

a * x + b * y = a * b - a - b.

Тогда перенесём:

a * x + b * y + a + b = a * b

a * (x + 1) + b * (y + 1) = a * b.

Теперь посмотрим по модулю a. Левая часть содержит b * (y + 1), значит

b * (y + 1) делится на a.

Так как gcd(a, b) = 1, число b обратимо по модулю a, значит y + 1 делится на a.

То есть y + 1 >= a, значит y >= a - 1.

Аналогично, рассматривая по модулю b, получаем, что x + 1 делится на b, значит x >= b - 1.

Тогда

a * x + b * y >= a * (b - 1) + b * (a - 1) = 2ab - a - b.

Но это больше, чем ab - a - b, противоречие.

Значит, число a * b - a - b действительно недостижимо.

Почему все большие числа достижимы

Рассмотрим a чисел:

n, n - b, n - 2b, ..., n - (a - 1)b.

Их остатки по модулю a все различны. Почему? Если бы два числа имели одинаковый остаток, то их разность делилась бы на a, то есть

(i - j) * b делилось бы на a.

Но gcd(a, b) = 1, значит тогда i - j делилось бы на a. Это невозможно для разных i, j из диапазона от 0 до a - 1.

Следовательно, среди этих a чисел есть ровно одно, которое делится на a. Пусть это

n - k * b = a * x.

Тогда

n = a * x + b * k.

Если при этом x >= 0, то число n представимо.

Теперь пусть n > a * b - a - b. Тогда

n - (a - 1)b > -a.

Значит, самое маленькое число из набора

n, n - b, ..., n - (a - 1)b

строго больше -a. А то число среди них, которое делится на a, обязано быть неотрицательным, потому что единственные кратные a, большие -a, это 0, a, 2a, ....

Значит, найдено представление n = a * x + b * k с x >= 0, k >= 0.

Итак, любое n > a * b - a - b достижимо.

Раз число a * b - a - b недостижимо, а все большие достижимы, оно и есть ответ.

5. Сложность

Алгоритм состоит из одного вычисления.

• Время: O(1)
• Память: O(1)

6. Код на C++17

#include <iostream>
using namespace std;

int main() {
    long long a, b;
    cin >> a >> b;
    cout << a * b - a - b << '\n';
    return 0;
}

7. Код на Python 3

a, b = map(int, input().split())
print(a * b - a - b)