Problème
Retournez le plus grand commun diviseur de a et b. L'algorithme d'Euclide remplace à chaque étape (a, b) par (b, a mod b) jusqu'à ce que b soit égal à 0.
Implémentez gcd(a, b).
Entrée
a : Le premier nombre. b : Le second nombre.
Sortie
Retournez gcd(a, b). gcd(0, 0) vaut 0.
Contraintes
0 ≤ a, b ≤ 10¹⁸
Exemples
Entrée :
a = 48
b = 18
Sortie attendue :
expected = 6Entrée :
long long a = 48;
long long b = 18;
Sortie attendue :
long long expected = 6;Entrée :
long a = 48;
long b = 18;
Sortie attendue :
long expected = 6;Explication
48 mod 18 = 12, 18 mod 12 = 6, 12 mod 6 = 0, donc la réponse est 6.
Entrée :
a = 17
b = 5
Sortie attendue :
expected = 1Entrée :
long long a = 17;
long long b = 5;
Sortie attendue :
long long expected = 1;Entrée :
long a = 17;
long b = 5;
Sortie attendue :
long expected = 1;Explication
17 et 5 n'ont aucun facteur commun autre que 1.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Le gcd ne change pas quand on remplace une paire par l’étape du reste.
Indice 2
Continuez à échanger les rôles des deux nombres jusqu’à ce que le second devienne zéro.
Indice 3
Pensez à gérer le cas où les deux entrées sont zéro.
Complexité attendue
temps O(log min(a, b)), espace supplémentaire O(1)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.