1. Идея

Автобусы приходят на остановку через равные промежутки времени:

• первый — каждые a минут,
• второй — каждые b минут.

Нужно найти самый ранний положительный момент времени, когда оба снова окажутся на остановке одновременно.

Такой момент должен делиться и на a, и на b. Значит, требуется найти наименьшее общее кратное чисел a и b, то есть НОК(a, b).

Чтобы вычислить НОК быстро и безопасно, используем связь с НОД:

• НОК(a, b) = a / НОД(a, b) * b

А сам НОД удобно находить алгоритмом Евклида.

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

1. Первый автобус будет на остановке в моменты: a, 2a, 3a, ...

2. Второй автобус будет на остановке в моменты: b, 2b, 3b, ...

3. Нам нужен первый общий момент из этих двух последовательностей.

4. По определению это и есть наименьшее общее кратное.

5. Перебирать моменты времени нельзя:

   • a и b могут быть до 10^9,
   • ответ может быть очень большим.

6. Поэтому нужен математический способ — через НОД.

3. Алгоритм

1. Считать a и b.
2. Найти g = НОД(a, b) алгоритмом Евклида.
3. Вычислить lcm = (a / g) * b.
4. Вывести lcm.

Алгоритм Евклида работает так:

• пока b != 0:
  • заменить (a, b) на (b, a % b)
• когда b станет равно 0, в a будет лежать НОД.

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

Пусть g = НОД(a, b).

Тогда числа a и b можно представить так:

• a = g * x
• b = g * y

где x и y взаимно просты.

Общее кратное чисел a и b должно содержать оба множителя g * x и g * y. Минимальное такое число равно:

• g * x * y

Подставим a = g * x:

• g * x * y = (a / g) * b

Значит, формула

НОК(a, b) = (a / НОД(a, b)) * b

даёт именно минимальное положительное число, которое кратно и a, и b.

Следовательно, это и есть первый момент, когда оба автобуса снова встретятся на остановке.

5. Сложность

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

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

Итого:

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

6. Код на C++17

#include <iostream>
using namespace std;

long long gcd_ll(long long a, long long b) {
    while (b != 0) {
        long long t = a % b;
        a = b;
        b = t;
    }
    return a;
}

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

    long long g = gcd_ll(a, b);
    long long lcm = (a / g) * b;

    cout << lcm << '\n';
    return 0;
}

7. Код на Python 3

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

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

g = x
lcm = (a // g) * b

print(lcm)