Когда снова вместе

В школьном дворе стоят два электронных табло. Первое «пикает» ровно каждые a секунд, второе — каждые b секунд. В момент времени 0 они пикнули одновременно.

Через сколько секунд они впервые снова пикнут одновременно?

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

Формат ввода

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

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

Выведите одно целое число — количество секунд до первого одновременного «пика» после момента 0.

Ограничения

• 1 ≤ a ≤ 10^9
• 1 ≤ b ≤ 10^9
• Все вычисления делайте в 64-битной целочисленной арифметике (в Python это не проблема).

Пример

Ввод 6 8

Вывод 24

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

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

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

• Считать a и b.
• Вычислить g = gcd(a, b) алгоритмом Евклида.
• Посчитать ответ как (a // g) * b.
• Вывести ответ.

Почему делим перед умножением: так меньше риск переполнения в языках с 64-битным int (в Python переполнения нет, но привычка полезная).

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

Частая ошибка: считать a * b / gcd(a, b) через обычное / и получить вещественное число или потерю точности. Нужны целочисленные операции: // и умножение.