А теперь к настоящим алгоритмам, а не использованию уже написанных в стандартной библиотеке. Читаем условие задачи:
Алгоритм Евклида - это, действительно, эффективный способ вычисления наибольшего общего делителя двух чисел. Но та версия, которую изучил Дима из условия задачи является неоптимальной. Давайте посмотрим на примере.
Если даны два числа 1000000 и 12, то шаг 4 будет выполняться очень много раз (83333), после чего a будет равно 4, а b - 12 (затем, они, конечно, поменяются местами). На примере мы можем заметить, что 1000000 = 83333 * 12 + 4, или в общем виде a = k * b + r. Отсюда становится понятно, что k равно целой части от деления a на b, а r - остатку от деления.
Таким образом, алгоритм Евклида можно реализовывать через операцию взятия остатка от деления. Время работы этой версии алгоритма оценивается теоремой Ламе, которая устанавливает связь алгоритма Евклида и последовательности Фибоначчи (Задача 147. Числа Фибоначчи):
Если b меньше n-го числа Фибоначчи, то алгоритм Евклида выполнит не более n - 2 итераций.
А так как числа Фибоначчи растут экспоненциально, значит алгоритм Евклида работает за логарифмическое время.
Но такая реализация алгоритма не подойдёт для решения задачи, потому что в ней пропускаются шаги (за счёт этого она и работает быстро). Но мы уже знаем, что в ней схлопываются лишь последовательности из шага 4, на котором изменяется только число a, причём все промежуточные значения удовлетворяют равенству a = k * b + r для некоторого k.
Значит, если бы где-то на шаге 4 встретилось число c, то оно бы тоже удовлетворяло условию c = k1 * b + r для некоторого k1. А значит a - c делилось бы без остатка на b. То есть для решения задачи надо лишь дописать эту проверку, когда b стало равно d.
Так как алгоритм очень быстрый, в этой задаче сделан мульти-тест - несколько входных данных в одном файле. Для начала считаем их количество и пройдём циклом:
Правильнее было бы в этом месте вызвать функцию с решением задачи для одного набора входных данных, но в нашем случае решение очень простое и короткое, поэтому можно разместить его прям здесь.
Считываем набор входных данных:
А дальше пишем алгоритм Евклида с добавленным условием:
В ветке else описана реализация алгоритма Евклида. Как мы видим, это очень простой алгоритм из одной строки (+ цикл).
Изменения коснулись условия работы цикла и дополнительной проверки внутри него. Обычно алгоритм работает до тех пор, пока b не станет равно 0, я дописал, чтобы он остановился, когда a == c и b == d. И когда условие внутри будет выполнено, искусственно приравниваю a к c, чтобы это стало последней итерацией цикла.
Так как цикл мог завершиться двумя способами: найден ответ или ответ не найден и b == 0, то при выводе результата необходимо сделать проверку:
Алгоритм Евклида - очень полезный алгоритм и часто используется, но стоит заметить, что иногда надо искать наибольший делитель очень больших чисел (используя длинную арифметику). В таком случае удобно применять бинарный алгоритм нахождения НОД, так как в нём используются лишь вычитание и умножение/деление на два. То есть не надо реализовывать деление длинного числа на длинное.
Предыдущий выпуск: Задача 498. K-перестановки
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.