2214. Функция 9

Напишите программу, которая вычисляет значение функции

f(m, n) =

Вход. Два натуральных числа n и m (1 ≤ n, m ≤ 10¹⁸).

Выход. Вывести значение фунции f(m, n).

Пример входа	Пример выхода
6 3	3

РЕШЕНИЕ

рекурсия

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

Функция f(m, n) вычисляет наибольший общий делитель (НОД) чисел m и n. Для решения задачи достаточно реализовать НОД двух чисел с использованием операции взятия модуля вместо вычитания.

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

Функция gcd возвращает наибольший общий делитель чисел a и b.

long long gcd(long long a, long long b)

{

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

}

Основная часть программы. Читаем входные данные n и m в порядке, заданном в условии задачи (сначала n, потом m).

scanf("%lld %lld", &n, &m);

Вычисляем и выводим значение f(m, n).

res = gcd(m, n);

printf("%lld\n", res);