Решение задачи "Необычное вычитание" с Codeforces

С пояснением   Просмотров: 20

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

Код 

#include <iostream>
using namespace std;

int main() {
	long long  a,b;
	cin >> a >> b;
	while (a!=0 and b!=0){
		if (a>=2*b){
			a = a%(2*b);
		}
		else if (b>=2*a){
			b = b%(2*a);
		}
		else {
			break;
		}
	}
	cout << a << " " << b;
	return 0;
}

         

Администратор Photo Автор: Администратор


Пояснение к задаче

Ответ на задачу может быть очень легко посчитан при помощи алгоритма Евклида (который описан в условии), только необходимо все вычитания заменить на взятия по модулю.

Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться