НОД и НОК


Отправить решение Решать в редакторе

Сложность: 15%
Очки: 100 (частичный балл)
Ограничение по времени: 1.0s
Ограничение по памяти: 256M

Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Даны два натуральных числа A и B. Найдите их наибольший общий делитель (НОД) и наименьшее общее кратное (НОК).

Входные данные

Одна строка: два целых числа A и B через пробел (1 ≤ A, B ≤ 1 000 000 000).

Выходные данные

Два целых числа через пробел: НОД(A, B) и НОК(A, B).

Пример 1

Вход:

12 18

Выход:

6 36

Пример 2

Вход:

7 13

Выход:

1 91

Пояснение

НОК может не поместиться в 32-битный тип — используйте 64-битные целые (long long в C++, long в Java/C#). Перебор делителей до min(A, B) работает слишком долго — воспользуйтесь алгоритмом Евклида.


Комментарии

Еще нет ни одного комментария.