Общий день двух расписаний

В школе есть два события: одно повторяется каждые a дней, другое — каждые b дней. Сегодня оба события случились в один день.

Определи, через сколько дней они снова совпадут в один и тот же день.

Важно: искомое число может быть больше, чем помещается в 32-битный тип (как на олимпиадах), хотя входные числа небольшие.

Формат ввода

В одной строке записаны два целых числа a и b.

Формат вывода

Выведи одно целое число — через сколько дней события снова совпадут.

Ограничения

• 1 ≤ a ≤ 1 000 000
• 1 ≤ b ≤ 1 000 000

Пример

Ввод:

6 15

Вывод:

30

Ключевое наблюдение: событие с периодом a бывает в дни, кратные a (a, 2a, 3a, …), а с периодом b — в дни, кратные b. Значит, следующий общий день — это наименьшее число, которое делится и на a, и на b, то есть НОК(a, b).

Почему работает приём: напрямую перебирать дни долго, зато есть связь НОК и НОД: lcm(a, b) = a / gcd(a, b) * b. НОД (наибольший общий делитель) быстро находится алгоритмом Евклида за логарифмическое время.

План решения:

• Прочитай a и b.
• Найди g = gcd(a, b) алгоритмом Евклида: пока b != 0 делай a, b = b, a % b.
• Посчитай ответ как l = (a // g) * b.
• Выведи l.

Сложность: O(log(min(a, b))) по времени и O(1) по памяти.

Частая ошибка: считать a * b // g. В Python это обычно безопасно, но в языках с фиксированными int можно получить переполнение. Правильнее делить раньше: (a // g) * b.