[原创]codeforces #200 div2.C Rational Resistance [思维]

2016-09-06 11:25:15 Tabris_ 阅读数：208

博客爬取于2020-06-14 22:43:30
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/52448350

题目链接：http://codeforces.com/contest/344/problem/C
--------------------------------------------------.
C. Rational Resistance
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
Mad scientist Mike is building a time machine in his spare time. To finish the work, he needs a resistor with a certain resistance value.

However, all Mike has is lots of identical resistors with unit resistance R0 = 1. Elements with other resistance can be constructed from these resistors. In this problem, we will consider the following as elements:

one resistor;
an element and one resistor plugged in sequence;
an element and one resistor plugged in parallel.
这里写图片描述
With the consecutive connection the resistance of the new element equals R = Re + R0. With the parallel connection the resistance of the new element equals . In this case Re equals the resistance of the element being connected.

Mike needs to assemble an element with a resistance equal to the fraction . Determine the smallest possible number of resistors he needs to make such an element.

Input
The single input line contains two space-separated integers a and b (1 ≤ a, b ≤ 1018). It is guaranteed that the fraction is irreducible. It is guaranteed that a solution always exists.

Output
Print a single number — the answer to the problem.

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is recommended to use the cin, cout streams or the %I64d specifier.

Examples
input
1 1
output
1
input
3 2
output
3
input
199 200
output
200
Note
In the first sample, one resistor is enough.

In the second sample one can connect the resistors in parallel, take the resulting element and connect it to a third resistor consecutively. Then, we get an element with resistance . 这里写图片描述We cannot make this element using two resistors.

------------------------.

题目大意： 就是有N个阻值为1的电阻 可以串联 可以并联 问最受用多少个电阻 能组成a/b这么个阻值

解题思路：

很好想 主要就是考虑串并联的公式 如果a/b>1的话 写成代分数 形式的话 前面整数部分用串联的方式一定会是最少的 然后接下来剩下的假分数的阻值 把它掉过来 接着这么运算就行了 直到最后分数变成了整数为止

上述就是思路了 聪明的你是不是也发现了 上述过程其实就是一个简单的辗转相除法 只要在其中加上一个记录[a/b]的过程就行了

附本题代码
---------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 505;
const double  Pi =  acos(-1);
# define pb push_back

LL ans = 0;
LL gcd(LL a,LL b)
{
    if(b==0)
        return a;
    else
    {
        ans+=a/b;
        return gcd(b,a%b);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    LL a,b;
    while(cin>>a>>b)
    {
        ans = 0;
        gcd(a,b);
        cout<<ans<<endl;
    }

    return 0;
}