Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-03-01 20:34:14.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:euclid2.in, euclid2.outSursăad-hoc
AutorArhiva EducationalaAdăugată defilipbFilip Cristian Buruiana filipb
Timp execuţie pe test0.125 secLimită de memorie4608 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Algoritmul lui Euclid

Cel mai mare divizor comun dintre doua numere naturale a si b este cel mai mare numar natural pozitiv d care divide ambele numere.

Cerinta

Dandu-se doua numere naturale a si b sa se calculeze cel mai mare divizor comun al lor.

Date de intrare

Fisierul de intrare euclid2.in contine pe prima linie doua numere naturale a si b.

Date de iesire

In fisierul de iesire euclid2.out se va afisa o singura linie ce contine rezultatul cerut.

Restrictii

  • 2 ≤ a, b ≤ 2 * 109

Exemplu

euclid2.ineuclid2.out
12 426

Indicatii de rezolvare

O scurta prezentare a acestui subiect gasiti aici.
Cel mai mare divizor comun dintre doua numere a si b se poate calcula iterativ, printr-o simpla parcurgere a tuturor numerelor de la 2 la minim(a, b). Aceasta rezolvare se gaseste aici si obtine 40 de puncte. Pentru a imbunatati timpul de rulare putem folosi algoritmul lui Euclid.
O solutie de 100 de puncte, pe ideea din articolul de mai sus, o gasiti aici.

Probleme similare

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content