Problem
Return the least common multiple of a and b, the smallest positive number that both divide. lcm(a, b) = a / gcd(a, b) × b.
Implement lcm(a, b).
Input
a: The first positive number. b: The second positive number.
Output
Return lcm(a, b).
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
Multiples of 4: 4, 8, 12…; multiples of 6: 6, 12…; the first common one is 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
A number's LCM with itself is the number: 7.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Use the relationship between gcd and lcm instead of searching for multiples.
Hinweis 2
Compute the gcd first, then combine the two numbers carefully.
Hinweis 3
Divide before multiplying to reduce overflow risk, even with large inputs.
Erwartete Komplexität
O(log min(a, b)) time, O(1) extra space
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.