Fişierul intrare/ieşire:euclid2.in, euclid2.outSursăad-hoc
AutorArhiva EducationalaAdăugată defilipbFilip Cristian Buruiana filipb
Timp execuţie pe test0.25 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 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.ineuclid2.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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content