← 返回题目列表

Codeforces · 343/A

A. 理性电阻

中文机器翻译题面 查看原题

疯狂科学家迈克正在业余时间建造一台时间机器。为了完成这项工作,他需要一个具有一定阻值的电阻。

然而,Mike 拥有的只是许多单位电阻 R0 = 1 的相同电阻器。可以用这些电阻器构建具有其他电阻的元件。在这个问题中,我们将考虑以下元素:

1.电阻1个;
2.依次插入一个元件和一个电阻;
3. 并联插入一个元件和一个电阻。

连续连接后,新元件的电阻等于 R = Re + R0。通过并联连接,新元件的电阻等于 $$R = \frac{1}{\frac{1}{R_{e}} + \frac{1}{R_{0}}}$$。在这种情况下,Re 等于所连接元件的电阻。

Mike 需要组装一个电阻等于分数 $${ \frac { a } { b } }$$ 的元件。确定制作这样一个元件所需的尽可能少的电阻器数量。

输入

单个输入行包含两个空格分隔的整数 a 和 b (1 ≤ a, b ≤ 1018)。保证分数 $${ \frac { a } { b } }$$ 是不可约的。保证解总是存在。

输出

打印一个数字——问题的答案。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。建议使用 cin、cout 流或 %I64d 说明符。

示例

输入 #1

1 1

输出 #1

1

输入 #2

3 2

输出 #2

3

输入 #3

199 200

输出 #3

200

注意

在第一个示例中,一个电阻就足够了。

在第二个示例中,可以并联连接电阻器,取出所得元件并将其连续连接到第三个电阻器。然后,我们得到一个电阻为 $$\frac{1}{\frac{1}{1}+\frac{1}{1}}+1=\frac{3}{2}$$ 的元素。我们不能使用两个电阻来制作这个元件。