Рус Uzb Eng

C17F. Рациональное сопротивление
Ограничение по времени: 2 cекунды
Ограничение по памяти: 64 мегабайт

Безумный ученый Майк в свободное время строит машину времени. Для окончания проекта ему понадобился резистор с определенным значением сопротивления. Однако у Майка в запасе есть только большое количество одинаковых резисторов с единичным сопротивлением R0=1. Элементы с другим сопротивлением можно собирать из данных резисторов. В данной задаче элементами будем считать: 1.один резистор; 2.элемент и один резистор, подключенные последовательно; 3.элемент и один резистор, подключенные параллельно.
При последовательном подключении сопротивление нового элемента равно R = Re + R0. При параллельном подключении сопротивление нового элемента равно . В данном случае Re равняется сопротивлению подключаемого элемента. Майку нужно собрать элемент с сопротивлением, равным дроби a / b . Определите наименьшее количество резисторов, с помощью которых можно собрать такой элемент.

Входные данные:
В единственной строке входных данных через пробел записаны два целых числа a и b (1 <= a, b <= 1018). Гарантируется, что дробь a / b несократима. Гарантируется, что решение всегда существует.

Выходные данные:
Выведите единственное число — ответ на задачу. Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Пример ввода Пример вывода
1 1
3 2
199 200
1
3
200
Область:
Источник задачи:

Отправить решение на проверку

Design by TUIT © 2012-2017 TUIT Online Judge. All rights reserved.