Este binecunoscut algoritmul de calcul al celui mai mare divizor comun (cmmdc) cu algoritmul lui Euclid prin împărţiri repetate. Conform acestui algoritm cmmdc a două numere naturale nenule a şi b se calculează păstrând restul împărţirii, şi reluând împărţirea cu vechiul împărţitor şi vechiul rest. Algoritmul se va termina când restul împărţirii devine zero. Cel mai mare divizor comun al celor două numere a şi b va fi ultimul împărţitor.
Pentru calculul celui mai mare divizor comun al perechii (16,22) se vor efectua succesiv împărţirile:
Vom numi un “pas” o operaţie de împărţire ce intervine în calculului cmmdc. Se observă că pentru determinarea cmmdc(16,22)=2 au fost necesari 5 paşi.
Cerinţă
Cunoscând valoarea unui număr natural n, realizaţi un program care determină o pereche de numere naturale (a,b) mai mici sau egale cu n, al căror cmmdc se obţine într-un număr maxim de paşi. Dacă există mai multe perechi (x,y) cu această proprietate se va afişa cea minimă. Spunem că perechea (a,b) este mai mică decât (x,y), dacă a<x sau a=x şi b<y.
Date de intrare
Fişierul text euclid.in conţine un singur număr natural n.
Date de ieşire
Fişierul text euclid.out va conţine pe prima linie numărul maxim de paşi determinat. A doua linie va conţine un număr natural a reprezentând primul număr al perechii minime identificate, iar pe a treia linie se va scrie numărul b reprezentând al doilea număr din pereche.
Restricţii
4 <= n <= 10200
Exemple
euclid.in
euclid.out
Explicaţii
8
5
5
8
Numărul maxim de paşi pentru oricare pereche de numere mai mici egale cu 8 este 5. Perechea (5,8) este minimă cu această proprietate.
12345678910
48
4807526976
7778742049
Numărul maxim de paşi pentru oricare pereche de numere mai mici egale cu 12345678910 este 48.
Perechea (4807526976,7778742049) este minimă cu această proprietate.
