Problem
Original anzeigen (Englisch)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).
Eingabe
a: Die erste Zahl. b: Die zweite Zahl.
Ausgabe
Gib gcd(a, b) zurück. gcd(0, 0) ist 0.
Einschränkungen
0 ≤ a, b ≤ 10¹⁸
Beispiele
Beispiel 1
Eingabe:
a = 48
b = 18
Erwartete Ausgabe:
expected = 6Eingabe:
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;Erläuterung
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 = 1Eingabe:
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;Erläuterung
17 und 5 haben keinen gemeinsamen Teiler außer 1.
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.