Разбор

Анализ алгоритма

Наименьшим общим кратным (НОК) двух целых чисел $a$ и $b$ называется наименьшее натуральное число, которое делится нацело на $a$ и на $b$. Например, НОК(2, 3) = 6, НОК(6, 10) = 30.

Для нахождения наименьшего общего кратного воспользуемся формулой:

Откуда

Поскольку $a$, $b$ < $2\ast 10^9$, то при умножении значение $a\ast b$ может выйти за пределы типа int. При вычислении следует воспользоваться типом long long.

Пример

Рассмотрим числа из примера:

откуда

Реализация алгоритма

Реализуем функции gcd (наибольший общий делитель) и lcm (наименьшее общее кратное).

long long gcd(long long a, long long b)
{
    return (!b) ? a : gcd(b, a % b);
}

long long lcm(long long a, long long b)
{
    return a / gcd(a, b) * b;
}

Основная часть программы. Читаем входные данные. Вычисляем и выводим ответ.

scanf("%lld %lld", &a, &b);
d = lcm(a, b);
printf("%lld\n", d);

Python реализация

def gcd(a, b):
    if a == 0: return b
    if b == 0: return a
    if a > b: return gcd(a % b, b)
    return gcd(a, b % a)

def lcm(a, b):
    return a // gcd(a, b) * b

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