1. Идея

Нужно понять, можно ли представить число c в виде a * x + b * y, где x и y — любые целые числа.

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

• уравнение a * x + b * y = c имеет целочисленное решение тогда и только тогда, когда c делится на gcd(a, b).

Так как в задаче разрешены и положительные, и отрицательные количества жетонов, никаких дополнительных ограничений на x и y нет. Значит, достаточно проверить только делимость.

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

Наблюдение 1

Все суммы вида a * x + b * y всегда делятся на gcd(a, b).

Почему так:

• g = gcd(a, b) делит a;
• g делит b;
• значит, g делит и a * x + b * y для любых целых x, y.

Следовательно, если c не делится на g, ответ сразу NO.

Наблюдение 2

Обратно тоже верно: если c делится на gcd(a, b), то нужное представление существует.

Это стандартное свойство алгоритма Евклида: все целые числа, кратные gcd(a, b), можно представить в виде a * x + b * y.

Наблюдение 3

В условии a и b могут быть отрицательными. Для НОД знак не важен, поэтому надо брать gcd(abs(a), abs(b)).

Наблюдение 4

По условию числа a и b не равны нулю одновременно. Значит, gcd(abs(a), abs(b)) всегда положителен, и деление по модулю корректно.

3. Алгоритм

1. Считать a, b, c.
2. Найти g = gcd(abs(a), abs(b)).
3. Если c % g == 0, вывести YES.
4. Иначе вывести NO.

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

Обозначим g = gcd(a, b).

Нужно проверить, существует ли решение уравнения:

a * x + b * y = c

для целых x и y.

Необходимость

Если решение существует, то число c равно a * x + b * y.

Так как g делит и a, и b, то g делит любую их целочисленную линейную комбинацию. Значит, g делит c.

Следовательно, если c не делится на g, решения быть не может.

Достаточность

По теореме Безу существуют такие целые x0 и y0, что

a * x0 + b * y0 = g.

Если c делится на g, то c = g * k для некоторого целого k.

Тогда, умножив равенство выше на k, получим:

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

Значит, решение существует.

Итак, условие существования решения ровно одно: c кратно gcd(a, b).

Именно это и проверяет алгоритм.

5. Сложность

Вычисление НОД работает за O(log(min(|a|, |b|))).

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

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

6. Код на C++17

#include <iostream>
#include <numeric>
#include <cstdlib>

using namespace std;

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

    long long g = gcd(llabs(a), llabs(b));

    if (c % g == 0) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }

    return 0;
}

7. Код на Python 3

from math import gcd

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

g = gcd(abs(a), abs(b))

if c % g == 0:
    print("YES")
else:
    print("NO")