Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | euclid2.in, euclid2.out | Sursă | ad-hoc |
| Autor | Arhiva Educationala | Adăugată de |  Filip Cristian Buruiana •filipb |
| Timp execuţie pe test | 0.125 sec | Limită de memorie | 4608 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.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.in | euclid2.out |
|---|---|
| 12 42 | 6 |
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
- cmmdc de pe infoarena
