Задача
Дана функция, аргументы которой — произвольные натуральные числа
$$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}$$
Составить алгоритм (написать программу), вычисляющий значение функции.
Вводные данные
Два натуральных числа $n$ и $m$ $(1\leq n, m \leq 10^{18}).$
Выходные данные
Искомое значение функции.
Тесты
| Входные данные | Выходные данные |
| $6$ $3$ | $3$ |
| $12$ $12$ | $12$ |
| $126$ $98$ | $98$ |
| $10329$ $1501$ | $1501$ |
| $1008359$ $15113$ | $15113$ |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
import java.util.*; class Main { public static void main (String[] args) { Scanner in = new Scanner(System.in); long n, m; n = in.nextLong(); m = in.nextLong(); System.out.print(f(n, m)); } static long f(long n, long m) { if (n % m == 0) return m; if (m % n == 0) return n; if (m > n) return f(m % n, n); else return f(n % m , m); } } |
Решение задачи
Для решения задачи напишем функцию f. Именно эта функция и будет считать искомое значение. Из условия задачи видим, что для решения потребуется рекурсия. Для этого, если остаток от деления одного натурального числа на другое не равен нулю, то мы снова возращаемся в функцию (в зависимости от того, что больше $n$ или $m$). Это будет продолжаться до тех пор, пока остаток от деления одного натурального числа на другое не будет равен нулю (как только $n \mod m = 0$ или $m \mod n = 0,$ то функция возращает в переменную искомое значение). Задача решена.
Ссылки
Условие задачи на e-olymp
Код решения на ideone.com