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. Din motive de eficienta putem folosi algoritmul lui Euclid.
Solutia oficiala (de 100 de puncte), pe ideea din articolul de mai sus, o gasiti aici.
Probleme similare
- cmmdc de pe infoarena
