Loading... ## 题面 ### 题目背景 $Jerry$教授又在给小老鼠讲课了。这回$Jerry$讲到了电学中电容的串并联,并给小老鼠留了搭电容的课后练习。但是$Jerry$还要继续备课,所以就请你帮忙给出标准答案了。 <!--more-->  ### 题目描述 电容,符号是$C$,单位是法拉($F$),然而这个单位太大了,$Jerry$会用皮法($pF$)来表述一个电容,$1pF = 10^{-12} F$。$Jerry$告诉你:两个容量为$C_1$和$C_2$的电容并联,会形成一个新的容量为$C_1 + C_2$的电容;两个容量为$C_1$和$C_2$的电容串联,会形成一个新的容量为$\frac{1}{\frac{1}{C_1} + \frac{1}{C_2}}$的电容。受困于技术原因,$Jerry$只能在原来的基础上每次并上一个$1pF$电容或者串上一个$1pF$电容,而不能搭了两个后再串一起或并一起。$Jerry$的练习题要求用若干容量为$1pF$的电容搭成一个容量为$\frac{a}{b} pF$的电容。$Jerry$手头的$1pF$电容不多了,他要求你用尽可能少的$1pF$电容来完成任务并告诉他最少要用多少个。 ### 输入格式 第一行一个正整数$T$,表示题目数量。 之后$T$行每行两个正整数$a$和$b$,表示这道题要求搭的电容容量为$\frac{a}{b} pF$。 ### 输出格式 共$T$行,每行一个整数,表示完成该题所用的最少$1pF$电容个数。 ### 样例 #### 输入样例1 ``` 2 1 1 3 2 ``` #### 输出样例1 ``` 1 3 ``` #### 输入样例2 ``` 2 6 5 199 200 ``` #### 输出样例2 ``` 6 200 ``` ### 数据规模与约定 对于20%的数据,$1 \le a \le 10$,$1 \le b \le 10$。 对于另外20%的数据,$a = 1$。 对于另外20%的数据,$b = 1$。 对于100%的数据,$1\le a \le 10^{18}$,$1 \le b \le 10^{18}$,$1 \le T \le 5000$。 ## 题意分析 首先因为只能串联或者并联上一个$1 pF$的电容,所以$C_2 = 1 pF$。公式就可以化成这样: 并联 : $C = C_1 + 1$ 串联 : $C = \frac{1}{\frac{1}{C_1} + 1} = \frac{1}{\frac{C_1 + 1}{C_1}} = \frac{C_1}{C_1 + 1}$ 然后DFS逆推,搜索每次应该串上一个还是并上一个。 记得先约分哦! ## AC代码 ```cpp #include <bits/stdc++.h> using namespace std; inline int rd() { register int ans = 0, flag = 1; register char c = getchar(); for (; c > '9' || c < '0'; c = getchar()) if (c == '-') flag = -1; for (; c >= '0' && c <= '9'; c = getchar()) ans = ans * 10 - '0' + c; return ans * flag; } inline long long rdll() { register long long ans = 0, flag = 1; register char c = getchar(); for (; c > '9' || c < '0'; c = getchar()) if (c == '-') flag = -1; for (; c >= '0' && c <= '9'; c = getchar()) ans = ans * 10 - '0' + c; return ans * flag; } long long gcd(long long a, long long b) { if (a < b) swap(a, b); return b ? gcd(b, a % b) : a; } long long ans = 0; void dfs(long long a, long long b) { if (a >= b) { ans += a / b; a %= b; } if (a != 0 && b != 0 && a % b != 0) { ans += b / a; b %= a; } if (a != 0 && b != 0) { dfs(a, b); } } long long solve(long long a, long long b) { ans = 0; long long gcdd = gcd(a, b); a /= gcdd; b /= gcdd; if (b == 1ll) return a; if (a == 1ll) return b; dfs(a, b); return ans; } int main() { int t = rd(); for (register int i = 1; i <= t; ++i) { printf("%lld\n", solve(rdll(), rdll())); } return 0; } ``` 最后修改:2019 年 12 月 07 日 09 : 56 PM © 允许规范转载 赞赏 如果觉得我的文章对你有用,请随意赞赏 ×Close 赞赏作者 扫一扫支付 支付宝支付 微信支付