Codeforces 343A Rational Resistance 题解
题意
你有很多个电阻器,一个电阻器$R_0$的电阻是$1$。
设一个电阻元件的电阻为$R$,可以由以下三种方式得到一个电阻元件
- 一个电阻器,则$R=R_0$。
- 一个电阻元件(电阻为$R_e$)串联一个电阻器,则$R=R_e+R_0$。
- 一个电阻元件(电阻为$R_e$)并联一个电阻器,则$R=\frac{1}{\frac{1}{R_e}+\frac{1}{R_0}}$。
给定一个最简分数$\frac{a}{b} (1\le a,b\le 10^{18})$,求至少要多少个电阻器 使得 得到的电阻元件的电阻为$\frac{a}{b}$。
题解
设有一个电阻元件的电阻为$\frac{x}{y}$。
串联后电阻为$\frac{x}{y}+1=\frac{x+y}{y}$。
并联后电阻为$\frac{1}{\frac{1}{\frac{x}{y}}+1}=\frac{x}{x+y}$。
那么
若$x>y$,则$\frac{x}{y}$是由$\frac{x-y}{y}$ 串联得出的。
若$x<y$,则$\frac{x}{y}$是由$\frac{x}{y-x}$ 并联得出的。
这样用大的数减小的数,就是辗转相减法,每减一次,答案加$1$。
但是数据范围太大,可以把辗转相减法转换成辗转相除法,每除一次,答案加 大数整除小数的结果。
程序
1 | // #pragma GCC optimize(2) |