Fişierul intrare/ieşire:euclid4.in, euclid4.outSursăLot Juniori 2008 - Baraj 5
AutorZoltan SzaboAdăugată detoni2007Pripoae Teodor Anton toni2007
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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:

DeimpartitImpartitorRestPas
16
22
16
Pasul 1
22
16
6
Pasul 2
16
6
4
Pasul 3
6
4
2
Pasul 4
4
2
0
Pasul 5

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 ≤ 10200

Exemplu

euclid4.ineuclid4.out
8
5
5
8
12345678910
48
4807526976
7778742049
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content