Олимпиадный тренинг

Задача . 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 после завершения работы алгоритма.

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

В первой строке записаны два целых числа n и m (1 ≤ n, m ≤ 10¹⁸). n — начальное значение переменной a, m — начальное значение переменной b.

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

Выведите два числа — значения a и b после завершения работы алгоритма.

Примечание

Пояснения к примерам:

a = 12, b = 5 $\text{[math]}$ a = 2, b = 5 $\text{[math]}$ a = 2, b = 1 $\text{[math]}$ a = 0, b = 1;
a = 31, b = 12 $\text{[math]}$ a = 7, b = 12.

№	Входные данные	Выходные данные
1	12 5	0 1
2	31 12	7 12

	Кол-во
С++ Mingw-w64	5

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Нет