题面

题目背景

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

Jerry

题目描述

电容,符号是$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代码

#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;
}
本文作者:Author:     文章标题:20191003模拟赛-T4 解题报告
本文地址:https://www.allenyou.wang/oi/20191003-T4.html     
版权说明:若无注明,本文皆为Allenyou's Blog原创,转载请保留文章出处。
Last modification:December 7th, 2019 at 09:56 pm