O proprietate interesanta a fractiilor ireductibile este ca orice fractie se poate obtine dupa urmatoarele reguli:
·
pe primul nivel se afla fractia
1/1;
·
pe al doilea nivel, īn stānga
fractiei 1/1 de pe primul nivel, plasam fractia 1/2
iar īn dreapta ei fractia 2/1;
nivelul 1: 1/1
nivelul 2: 1/2 2/1
· pe fiecare nivel k se plaseaza sub fiecare fractie i/j de pe nivelul de deasupra, fractia i/(i+j) īn stānga, iar fractia (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
Cerinta
Dāndu-se o fractie oarecare prin numaratorul si numitorul sau, determinati numarul nivelului pe care se afla fractia sau o fractie echivalenta (avānd aceeasi valoare) cu aceasta.
Fisier de intrare: FRACTII.IN
Linia 1: N M
· doua numere naturale nenule, separate printr-un spatiu, reprezentānd numaratorul si numitorul unei fractii (numarator respectiv numitor).
Fisier de iesire: FRACTII.OUT
Linia 1: niv
· numar natural nenul, reprezentānd numarul nivelului care corespunde fractiei.
· 1 < N,M <= 2000000000 (doua miliarde)
FRACTII.IN
13 8
FRACTII.OUT
6
FRACTII.IN
12 8
FRACTII.OUT
3
Timp maxim de executare/per test: 1 secunda