Решение задачи Необычное вычитание с Codeforces
С пояснением   Просмотров: 67
Даны две переменные a и b. Рассмотрим следующую последовательность действий над этими переменными:
Если a = 0 или b = 0, закончить процесс. Иначе перейти к шагу 2;
Если a ≥ 2·b, то присвоить a значение a - 2·b и повторить шаг 1. Иначе перейти к шагу 3;
Если b ≥ 2·a, то присвоить b значение b - 2·a и повторить шаг 1. Иначе закончить процесс.
Изначально значения a и b — положительные целые числа, поэтому алгоритм отработает за конечное время.
Определите значения a и b после завершения работы алгоритма.
Если a = 0 или b = 0, закончить процесс. Иначе перейти к шагу 2;
Если a ≥ 2·b, то присвоить a значение a - 2·b и повторить шаг 1. Иначе перейти к шагу 3;
Если b ≥ 2·a, то присвоить b значение b - 2·a и повторить шаг 1. Иначе закончить процесс.
Изначально значения a и b — положительные целые числа, поэтому алгоритм отработает за конечное время.
Определите значения a и b после завершения работы алгоритма.
Пояснение к задаче
Ответ на задачу может быть очень легко посчитан при помощи алгоритма Евклида (который описан в условии), только необходимо все вычитания заменить на взятия по модулю.