CF343A Rational Resistance

疯狂科学家 Mike 正在业余时间制造一台时光机。要完成这项工作，他需要一个具有特定电阻值的电阻器。 然而，Mike 手头上只有很多相同的单位电阻器，电阻值为 $R_0 = 1$。可以通过这些电阻器组合得到其他电阻值的元件。在本题中，下述情况都被视为“元件”： 1. 一个电阻器； 2. 一个元件和一个电阻器串联； 3. 一个元件和一个电阻器并联。 串联时，新元件的电阻为 $R = R_e + R_0$。并联时，新元件的电阻为 $R = \frac{R_e \cdot R_0}{R_e + R_0}$，其中 $R_e$ 为被连接元件的电阻。 Mike 需要组装出一个电阻恰好等于 $\frac{a}{b}$ 的元件。请判断，至少需要多少个电阻器才能实现。

输入包含一行，两个以空格分隔的整数 $a$ 和 $b$（$1 \leq a, b \leq 10^{18}$）。保证分数 $\frac{a}{b}$ 是最简分数，且保证一定有解。

输出一个整数，表示最少需要多少个电阻器。

在第一个样例中，只需一个电阻器即可。 在第二个样例中，可以先将两个电阻器并联，再把所得元件与第三个电阻器串联。这样可获得电阻 $\frac{3}{2}$。用两个电阻器无法得到该电阻值。 由 ChatGPT 5 翻译