Rational Resistance

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 R 0 = 1. Elements with other resistance can be constructed from these resistors. In this problem, we will consider the following as elements:

  1. one resistor;
  2. an element and one resistor plugged in sequence;
  3. an element and one resistor plugged in parallel.

With the consecutive connection the resistance of the new element equals R = R e + R 0. With the parallel connection the resistance of the new element equals . In this case R e 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.


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.


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.



1 1




3 2




199 200




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.


#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <set>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <memory.h>
#include <string>
#include <sstream>
#include <cstdlib>
#include <ctime>
#include <cassert>

using namespace std;

int main() {
long long a, b;
cin >> a >> b;
long long ans = 0;
while (a > 0 && b > 0) {
if (a > b) {
ans += a / b;
a %= b;
} else {
ans += b / a;
b %= a;
cout << ans << endl;
  return 0;