301813: CF343A. Rational Resistance

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Rational Resistance

题意翻译

#### 题意翻译简化: 迈克有许多阻值为 $1Ω$ 的电阻,通过串联、并联的方式组装为一个电阻为 $\frac{a}{b}$ 的元件,求所需的最少电阻数量。 #### 数据: $1<=a,b<=10^{18}$,保证 $\frac{a}{b}$ 已经最简,保证有解。

题目描述

Mad scientist Mike is building a time machine in his spare time. To finish the work, he needs a resistor with a certain resistance value. However, all Mike has is lots of identical resistors with unit resistance $ R_{0}=1 $ . Elements with other resistance can be constructed from these resistors. In this problem, we will consider the following as elements: 1. one resistor; 2. an element and one resistor plugged in sequence; 3. an element and one resistor plugged in parallel. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF343A/f117fcf32ddafc80e319e28fce885c21483edc5b.png)With the consecutive connection the resistance of the new element equals $ R=R_{e}+R_{0} $ . With the parallel connection the resistance of the new element equals ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF343A/a708eb8090c66cbbd34afced0c36506bcb612681.png). In this case $ R_{e} $ equals the resistance of the element being connected. Mike needs to assemble an element with a resistance equal to the fraction ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF343A/eecd60ed91fbeebe74e2406ea1a11d26df905945.png). Determine the smallest possible number of resistors he needs to make such an element.

输入输出格式

输入格式


The single input line contains two space-separated integers $ a $ and $ b $ ( $ 1<=a,b<=10^{18} $ ). It is guaranteed that the fraction ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF343A/eecd60ed91fbeebe74e2406ea1a11d26df905945.png) is irreducible. It is guaranteed that a solution always exists.

输出格式


Print a single number — the answer to the problem. Please do not use the %lld specifier to read or write 64-bit integers in С++. It is recommended to use the cin, cout streams or the %I64d specifier.

输入输出样例

输入样例 #1

1 1

输出样例 #1

1

输入样例 #2

3 2

输出样例 #2

3

输入样例 #3

199 200

输出样例 #3

200

说明

In the first sample, one resistor is enough. In the second sample one can connect the resistors in parallel, take the resulting element and connect it to a third resistor consecutively. Then, we get an element with resistance ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF343A/234023ef6c61445a95e9903d46cd7846f3823141.png). We cannot make this element using two resistors.

Input

题意翻译

#### 题意翻译简化: 迈克有许多阻值为 $1Ω$ 的电阻,通过串联、并联的方式组装为一个电阻为 $\frac{a}{b}$ 的元件,求所需的最少电阻数量。 #### 数据: $1<=a,b<=10^{18}$,保证 $\frac{a}{b}$ 已经最简,保证有解。

加入题单

上一题 下一题 算法标签: