1183. Коробки

Есть две коробки. В первой находится a шаров, во второй b (0 < a + b < 2147483648). Шары разрешается перекладывать из одной коробки в другую. Причем перекладывать в любую из коробок можно только столько шаров, сколько в ней находится. Необходимо определить, можно ли все шары сложить в одну коробку.

Вход. Каждая строка содержит два целых числа a и b, разделенных пробелом.

Выход. Для каждого теста в отдельной строке вывести количество перекладываний, необходимое для того чтобы все шары находились в одной коробке, или -1, если это сделать невозможно.

Пример входа	Пример выхода
2 6 8 12 7 9	2 -1 4

РЕШЕНИЕ

математика - НОД

Анализ алгоритма

Все шары можно переложить в одну коробку тогда и только тогда, когда

a + b = НОД (a, b) * 2^k

для некоторого натурального k. Если указанное равенство не выполняется, то выводим -1. Иначе моделируем процесс перекладывания шаров, как указано в условии задачи.

Реализация алгоритма

Функция move моделирует процесс перекладывания шаров и возвращает количество перекладываний, после выполнения которых все шары будут находиться в одной коробке.

int move(int a, int b)

{

if (a == 0 || b == 0) return 0;

if (a > b) return move(a - b, 2 * b) + 1;

return move(2 * a, b - a) + 1;

}

Проверяем, можно ли шары переложить в одну коробку. Для этого проверяем выполнение равенства a + b = НОД (a, b) * 2^k для некоторого натурального k.

int Can(int a, int b)

{

int res = (a + b) / gcd(a,b);

while(res % 2 == 0) res /= 2;

return res == 1;

}

Основная часть программы. Читаем входные данные и выводим результат.

while (scanf("%d %d", &a, &b) == 2)

if (Can(a, b)) printf("%d\n", move(a, b));

else printf("-1\n");