Se citesc doua numere naturale a si b. Determinati cel mai mare divizor comun al lor, folosind algoritmul lui Euclid binar (algoritmul lui Stein), care foloseste doar operatii pe biti (deplasari si scaderi), fara impartiri.
- Date de intrare
- Se citesc a si b.
- Date de iesire
- Se afiseaza cel mai mare divizor comun al lui a si b.
- Restrictii
- 0 <= a, b <= 10^18, cel putin unul dintre a, b este nenul
Exemple
Exemplul 1
Intrare
48 18
Iesire
6
Exemplul 2
Intrare
17 13
Iesire
1