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 T perechi de numere naturale (a, b), sa se calculeze cel mai mare divizor comun al numerelor din fiecare pereche in parte.
Date de intrare
Fisierul de intrare euclid2.in contine pe prima linie numarul T de perechi. Urmatoarele T linii contin cate doua numere naturale a si b.
Date de iesire
In fisierul de iesire euclid2.out se vor scrie T linii. A i-a linie din acest fisier contine cel mai mare divizor comun al numerelor din perechea de pe linia i+1 din fisierul de intrare.
Restrictii
- 1 ≤ T ≤ 100 000
- Pentru fiecare pereche, 2 ≤ a, b ≤ 2 * 109
Exemplu
| euclid2.in | euclid2.out |
|---|---|
| 3 12 42 21 7 9 10 | 6 7 1 |
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 30 de puncte. Pentru a imbunatati timpul de rulare putem folosi algoritmul lui Euclid prin scaderi, ceea ce duce la obtinerea a 60 de puncte, sau prin impartiri, solutie ce obtine punctajul maxim.
Probleme similare
- cmmdc de pe infoarena
