Größter gemeinsamer Teiler

Problem

Gib den größten gemeinsamen Teiler von a und b zurück. Euklids Algorithmus ersetzt wiederholt (a, b) durch (b, a mod b), bis b gleich 0 ist.

Implementiere gcd(a, b).

a: Die erste Zahl. b: Die zweite Zahl.

Gib gcd(a, b) zurück. gcd(0, 0) ist 0.

0 ≤ a, b ≤ 10¹⁸

Beispiel 1

Eingabe:
a = 48
b = 18

Erwartete Ausgabe:
expected = 6

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

Erwartete Ausgabe:
long long expected = 6;

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

Erwartete Ausgabe:
long expected = 6;

48 mod 18 = 12, 18 mod 12 = 6, 12 mod 6 = 0, daher ist die Antwort 6.

Beispiel 2

Eingabe:
a = 17
b = 5

Erwartete Ausgabe:
expected = 1

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

Erwartete Ausgabe:
long long expected = 1;

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

Erwartete Ausgabe:
long expected = 1;

17 und 5 haben keinen gemeinsamen Teiler außer 1.

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Der gcd ändert sich nicht, wenn du ein Paar durch den Restschritt ersetzt.

Hinweis 2

Tausche die Rollen der beiden Zahlen immer wieder, bis die zweite null wird.

Hinweis 3

Achte darauf, den Fall zu behandeln, in dem beide Eingaben null sind.

Erwartete Komplexität

Zeit O(log min(a, b)), zusätzlicher Speicher O(1)

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.