e-olymp 2214. Функция 9

Задача

Дана функция, аргументы которой — произвольные натуральные числа

[latex]f(M,N)=\begin{cases} f(M-N,N), & \text{ npu } M>N \\ N, & \text{ npu } M=N \\ f(N-M,M) & \text{ npu } N>M \end{cases}[/latex]

Составить алгоритм (написать программу), вычисляющий значение функции.

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

Два натуральных числа [latex]n[/latex] и [latex]m[/latex] [latex](1 \le n, m \le 10^{18})[/latex].

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

Искомое значение функции.

Тесты

Входные данные Выходные данные
[latex]6[/latex] [latex]3[/latex] [latex]3[/latex]
[latex]12[/latex] [latex]12[/latex] [latex]12[/latex]
[latex]126[/latex] [latex]98[/latex] [latex]98[/latex]
[latex]10329[/latex] [latex]1501[/latex] [latex]1501[/latex]
[latex]1008359[/latex] [latex]15113[/latex] [latex]15113[/latex]

Код программы

Решение задачи

Для решения задачи напишем функцию [latex]f[/latex]. Именно эта функция и будет считать искомое значение. Из условия задачи видим, что для решения потребуется рекурсия. Для этого, если остаток от деления одного натурального числа на другое не равен нулю, то мы снова возращаемся в функцию (в зависимости от того,
что больше [latex]m[/latex] или [latex]n[/latex]). Это будет продолжаться до тех пор, пока остаток от деления одного натурального числа на другое не будет равен нулю (как только $n\mod m = 0$ или $m\mod n = 0$, то функция возращает в переменную [latex]t[/latex] искомое значение). Задача решена.

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com