НОД и НОК
Отправить решение
Решать в редакторе
Сложность:
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) работает слишком долго — воспользуйтесь алгоритмом Евклида.
Комментарии