euclid4

Euclid4

== include(page="template/taskheader" task_id="euclid4") ==

Poveste si cerinta...

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:
 
table. |_. Deimpartit |_. Impartitor |_. Rest|_. Pas |
| 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.
 
h2. 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$.

h2. Date de intrare

Fisierul de intrare $euclid4.in$ ...

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

h2. Date de iesire

In fisierul de iesire $euclid4.out$ ...

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.

h2. Restrictii

* $... ≤ ... ≤ ...$

* $4 ≤ n ≤ 10^200^$

h2. Exemplu
table(example). |_. euclid4.in |_. euclid4.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicatie
 
...

| 8
| 5
  5
  8
|
| 12345678910
| 48
  4807526976
  7778742049
|

== include(page="template/taskfooter" task_id="euclid4") ==

3344