1. Идея

Нужно проверить, имеют ли числа a и b общий делитель больше 1.

Если такого делителя нет, то числа взаимно простые, а значит шестерёнки считаются совместимыми.
Это ровно означает, что их наибольший общий делитель равен 1.

Значит задача сводится к вычислению НОД(a, b):

• если НОД(a, b) = 1, выводим YES;
• иначе выводим NO.

Для нахождения НОД удобно использовать алгоритм Евклида.

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

Наблюдение 1

По условию шестерёнки совместимы тогда и только тогда, когда у чисел a и b нет общего делителя больше 1.

Это стандартное определение взаимной простоты:

• 6 и 35 — взаимно простые, потому что их НОД равен 1;
• 12 и 18 — не взаимно простые, потому что их НОД равен 6.

Наблюдение 2

Алгоритм Евклида позволяет быстро находить НОД двух чисел с помощью повторения операции:

• заменяем пару (a, b) на (b, a % b),
• пока b не станет равно 0.

Когда b = 0, текущее значение a и есть НОД исходных чисел.

Наблюдение 3

Ограничения до 10^18 довольно большие, поэтому перебирать делители нельзя.
Но алгоритм Евклида работает очень быстро даже для таких чисел.

3. Алгоритм

1. Считать числа a и b.
2. Пока b != 0:
   • вычислить остаток r = a % b;
   • присвоить a = b;
   • присвоить b = r.
3. После завершения цикла в a хранится НОД исходных чисел.
4. Если a == 1, вывести YES, иначе вывести NO.

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

Основа решения — свойство НОД:

НОД(a, b) = НОД(b, a % b).

Почему это верно:

• любой общий делитель чисел a и b делит и число a - k * b, а значит делит остаток a % b;
• наоборот, любой общий делитель чисел b и a % b делит и число a, потому что a можно представить как b * k + (a % b).

Значит множество общих делителей у пар (a, b) и (b, a % b) одинаковое, а значит одинаков и наибольший общий делитель.

Мы повторяем это преобразование, пока второе число не станет нулём.
Когда получаем пару (a, 0), НОД равен a, потому что НОД числа и нуля — это само число.

После этого остаётся только проверить:

• если НОД равен 1, общих делителей больше 1 нет, значит ответ YES;
• если НОД больше 1, такой общий делитель существует, значит ответ NO.

5. Сложность

Алгоритм Евклида работает за O(log(min(a, b))).

Память: O(1).

6. Код на C++17

#include <iostream>
using namespace std;

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

    while (b != 0) {
        long long r = a % b;
        a = b;
        b = r;
    }

    if (a == 1) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }

    return 0;
}

7. Код на Python 3

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

while b != 0:
    a, b = b, a % b

if a == 1:
    print("YES")
else:
    print("NO")