O proprietate interesanta a fracțiilor ireductibile este ca orice fracție se poate obține după următoarele reguli:

O proprietate interesanta a fracțiilor ireductibile este ca orice fracție se poate obține după următoarele reguli:
– pe primul nivel se afla fracția 1/1;
– pe al doilea nivel, în stânga fracției 1/1 de pe primul nivel, plasam fracția 1/2 iar în dreapta ei fracția 2/1;

nivelul 1: 1/1
nivelul 2: 1/2 2/1

– pe fiecare nivel k se plasează sub fiecare fracție i / j de pe nivelul de deasupra, fracția i / (i + j) în stânga, iar fracția (i + j) / j în dreapta.

nivelul 1: 1/1
nivelul 2: 1/2 2/1
nivelul 3: 1/3 3/2 2/3 3/1

Cerința

Dându-se o fracție oarecare prin numărătorul și numitorul său, determinați numărul nivelului pe care se află fracția sau o fracție echivalentă (având aceeași valoare) cu aceasta.

Date de intrare

Fișierul de intrare fractzii.in conține pe prima linie două numere naturale nenule N M, separate printr-un spațiu, reprezentând numărătorul și respectiv numitorul unei fracții.

Date de ieșire

Fișierul de ieșire fractzii.out va conţine o ingură linie, pe care va fi scris număr natural nenul, reprezentând numărul nivelului care corespunde fracţiei.

Restricții și precizări

• 1 ≤ N, M ≤ 2 000 000 000

Exemplul 1:

fractzii.in

13 8

fractzii.out

6

Exemplul 2:

fractzii.in

12 8

fractzii.out

3

#include <bits/stdc++.h>
using namespace std;
ifstream cin("fractzii.in");
ofstream cout("fractzii.out");
int cmmdc(int a , int b)
{
    if(b != 0) return a / b + cmmdc(b , a % b);
    else return 0;
}
int main()
{
    int n ,c;
    cin >> n >> c;
    cout << cmmdc(n ,c );
}