# PBinfo #2308 – Fractzii – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

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

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
using namespace std;
int Cmmdc(int a, int b)
{
    int r;
    while (b > 0)
    {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}
int main()
{
    int n, m, c, niv = 0;
    ifstream fin("fractzii.in");
    ofstream fout("fractzii.out");
    fin >> n >> m;
    c = Cmmdc(n, m);
    n /= c;
    m /= c;
    while (n != 1 && m != 1)
    {
        if (n > m)
        {
            niv += (n / m);
            n = n % m;
        }
        else
        {
            niv += (m  / n);
            m = m % n;
        }
    }
    niv += max(n, m);
    fout << niv << "\n";
    fout.close();
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/2308)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/2308/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-2308/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)