Задача 527. Алгоритм Евклида

Алгоритм Евклида - это, действительно, эффективный способ вычисления наибольшего общего делителя двух чисел. Но та версия, которую изучил Дима из условия задачи является неоптимальной. Давайте посмотрим на примере.

Если даны два числа 1000000 и 12, то шаг 4 будет выполняться очень много раз (83333), после чего a будет равно 4, а b - 12 (затем, они, конечно, поменяются местами). На примере мы можем заметить, что 1000000 = 83333 * 12 + 4, или в общем виде a = k * b + r. Отсюда становится понятно, что k равно целой части от деления a на b, а r - остатку от деления.

Таким образом, алгоритм Евклида можно реализовывать через операцию взятия остатка от деления. Время работы этой версии алгоритма оценивается теоремой Ламе, которая устанавливает связь алгоритма Евклида и последовательности Фибоначчи (Задача 147. Числа Фибоначчи):