| Codeforces Round 200 (Div. 1) |
|---|
| Закончено |
Безумный ученый Майк в свободное время строит машину времени. Для окончания проекта ему понадобился резистор с определенным значением сопротивления.
Однако у Майка в запасе есть только большое количество одинаковых резисторов с единичным сопротивлением R0 = 1. Элементы с другим сопротивлением можно собирать из данных резисторов. В данной задаче элементами будем считать:
- один резистор;
- элемент и один резистор, подключенные последовательно;
- элемент и один резистор, подключенные параллельно.
При последовательном подключении сопротивление нового элемента равно R = Re + R0. При параллельном подключении сопротивление нового элемента равно 
. В данном случае Re равняется сопротивлению подключаемого элемента.
Майку нужно собрать элемент с сопротивлением, равным дроби 
. Определите наименьшее количество резисторов, с помощью которых можно собрать такой элемент.
В единственной строке входных данных через пробел записаны два целых числа a и b (1 ≤ a, b ≤ 1018). Гарантируется, что дробь несократима. Гарантируется, что решение всегда существует.
Выведите единственное число — ответ на задачу.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
1 1
1
3 2
3
199 200
200
В первом примере хватает одного резистора.
Во втором примере можно соединить два резистора параллельно, а полученный элемент соединить последовательно с третьим резистором. Таким образом получаем элемент с сопротивлением 
. С помощью двух резисторов такой элемент построить невозможно.
