Fişierul intrare/ieşire:	euclid4.in, euclid4.out	Sursă	Lot Juniori 2008 - Baraj 5
Autor	Zoltan Szabo	Adăugată de	Pripoae Teodor Anton •toni2007
Timp execuţie pe test	0.05 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Euclid4

Este binecunoscut algoritmul de calcul al celui mai mare divizor comun (cmmdc) cu algoritmul lui Euclid prin impartiri repetate. Conform acestui algoritm cmmdc a doua numere naturale nenule a si b se calculeaza pastrand restul impartirii, si reluand impartirea cu vechiul impartitor si vechiul rest. Algoritmul se va termina cand restul impartirii devine zero. Cel mai mare divizor comun al celor doua numere a si b va fi ultimul impartitor.
Pentru calculul celui mai mare divizor comun al perechii (16,22) se vor efectua succesiv impartirile:

Vom numi un pas o operatie de impartire ce intervine in calculului cmmdc. Se observa ca pentru determinarea cmmdc(16,22)=2 au fost necesari 5 pasi.

Cerinta

Cunoscand valoarea unui numar natural n, realizati un program care determina o pereche de numere naturale (a,b) mai mici sau egale cu n, al caror cmmdc se obtine intr-un numar maxim de pasi. Daca exista mai multe perechi (x,y) cu aceasta proprietate se va afisa cea minima. Spunem ca perechea (a,b) este mai mica decat (x,y), daca a<x sau a=x si b<y.

Date de intrare

Fisierul de intrare euclid4.in contine un singur numar natural n

Date de iesire

Fisierul de iesire euclid4.out va contine pe prima linie numarul maxim de pasi determinat. A doua linie va contine un numar natural a reprezentand primul numar al perechii minime identificate, iar pe a treia linie se va scrie numarul b reprezentand al doilea numar din pereche.

Restrictii

• 4 ≤ n ≤ 10²⁰⁰

Exemplu

Cum se trimit solutii?