Maior Divisor Comum

Problema

Retorne o maior divisor comum de a e b. O algoritmo de Euclides substitui repetidamente (a, b) por (b, a mod b) até que b seja 0.

Implemente gcd(a, b).

a: O primeiro número. b: O segundo número.

Retorne gcd(a, b). gcd(0, 0) é 0.

0 ≤ a, b ≤ 10¹⁸

Exemplo 1

Entrada:
a = 48
b = 18

Saída esperada:
expected = 6

Entrada:
long long a = 48;
long long b = 18;

Saída esperada:
long long expected = 6;

Entrada:
long a = 48;
long b = 18;

Saída esperada:
long expected = 6;

48 mod 18 = 12, 18 mod 12 = 6, 12 mod 6 = 0, então a resposta é 6.

Exemplo 2

Entrada:
a = 17
b = 5

Saída esperada:
expected = 1

Entrada:
long long a = 17;
long long b = 5;

Saída esperada:
long long expected = 1;

Entrada:
long a = 17;
long b = 5;

Saída esperada:
long expected = 1;

17 e 5 não possuem nenhum fator em comum além de 1.

Tente sozinho primeiro e depois abra uma dica de cada vez.

Dica 1

O gcd não muda quando você troca um par pela etapa do resto.

Dica 2

Continue trocando os papéis dos dois números até o segundo virar zero.

Dica 3

Não esqueça de tratar o caso em que ambos os inputs são zero.

Complexidade esperada

tempo O(log min(a, b)), espaço extra O(1)

Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.