20 БАЛЛОВ. пж срочно
Модифицированный алгоритм Евклида для вычисления наибольшего общего делителя двух натуральных чисел, формулируется так: нужно заменять большее число на остаток от деления большего на меньшее до тех пор, пока остаток не станет равно нулю; тогда второе число и есть НОД. Напишите программу, которая реализует этот алгоритм.
Входные данные
Входная строка содержит два числа, разделённые пробелом – a и b .
Выходные данные
Программа должна вывести в одной строке два числа: сначала наибольший общий делитель двух введённых чисел, а затем – количество шагов цикла, которые были выполнены.
Примеры
входные данные
21 14
выходные данные
7 2
входные данные
121 136
выходные данные
1 3
В С++ Пожалуйста