Problema
Restituisci il massimo comun divisore di a e b. L'algoritmo di Euclide sostituisce ripetutamente (a, b) con (b, a mod b) finché b è 0.
Implementa gcd(a, b).
Input
a: Il primo numero. b: Il secondo numero.
Output
Restituisci gcd(a, b). gcd(0, 0) è 0.
Vincoli
0 ≤ a, b ≤ 10¹⁸
Esempi
Input:
a = 48
b = 18
Output atteso:
expected = 6Input:
long long a = 48;
long long b = 18;
Output atteso:
long long expected = 6;Input:
long a = 48;
long b = 18;
Output atteso:
long expected = 6;Spiegazione
48 mod 18 = 12, 18 mod 12 = 6, 12 mod 6 = 0, quindi la risposta è 6.
Input:
a = 17
b = 5
Output atteso:
expected = 1Input:
long long a = 17;
long long b = 5;
Output atteso:
long long expected = 1;Input:
long a = 17;
long b = 5;
Output atteso:
long expected = 1;Spiegazione
17 e 5 non hanno fattori comuni oltre a 1.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Il gcd non cambia se sostituisci la coppia con il passo del resto.
Suggerimento 2
Continua a scambiare il ruolo dei due numeri finché il secondo non diventa zero.
Suggerimento 3
Assicurati di gestire il caso in cui entrambi gli input siano zero.
Complessità attesa
tempo O(log min(a, b)), spazio aggiuntivo O(1)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.