20191003模拟赛-T4 解题报告

2019 年 10 月 13 日

742次浏览

1950字数

## 题面
### 题目背景
$Jerry$教授又在给小老鼠讲课了。这回$Jerry$讲到了电学中电容的串并联，并给小老鼠留了搭电容的课后练习。但是$Jerry$还要继续备课，所以就请你帮忙给出标准答案了。

![Jerry](https://blog-oss.allenyou.wang/2019/12/07/10ed6185a4dd2.png)
### 题目描述
电容，符号是$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

如果觉得我的文章对你有用，请随意赞赏

20191003模拟赛-T4 解题报告