Розбір

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

Найменшим спільним кратним (НСК) двох цілих чисел $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))