Problem
Gib das kleinste gemeinsame Vielfache von a und b zurück, also die kleinste positive Zahl, die durch beide teilbar ist. lcm(a, b) = a / gcd(a, b) × b.
Implementiere lcm(a, b).
Eingabe
a: Die erste positive Zahl. b: Die zweite positive Zahl.
Ausgabe
Gib lcm(a, b) zurück.
Einschränkungen
1 ≤ a, b ≤ 1.000.000.000
Beispiele
Eingabe:
a = 4
b = 6
Erwartete Ausgabe:
expected = 12Eingabe:
long long a = 4;
long long b = 6;
Erwartete Ausgabe:
long long expected = 12;Eingabe:
long a = 4;
long b = 6;
Erwartete Ausgabe:
long expected = 12;Erläuterung
Vielfache von 4: 4, 8, 12…; Vielfache von 6: 6, 12…; das erste gemeinsame ist 12.
Eingabe:
a = 7
b = 7
Erwartete Ausgabe:
expected = 7Eingabe:
long long a = 7;
long long b = 7;
Erwartete Ausgabe:
long long expected = 7;Eingabe:
long a = 7;
long b = 7;
Erwartete Ausgabe:
long expected = 7;Erläuterung
Das kgV einer Zahl mit sich selbst ist die Zahl: 7.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Nutze die Beziehung zwischen gcd und lcm statt nach Vielfachen zu suchen.
Hinweis 2
Berechne zuerst den gcd und kombiniere dann die beiden Zahlen sorgfältig.
Hinweis 3
Teile vor dem Multiplizieren, um das Risiko eines Überlaufs zu verringern, auch bei großen Eingaben.
Erwartete Komplexität
Zeit O(log min(a, b)), zusätzlicher Speicher O(1)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.