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 赞赏作者 扫一扫支付 支付宝支付 微信支付
