Problem
Eine Bäckerei packt Kekse in Schachteln aller Größen von lo bis hi. Sie sucht eine Keksmenge, mit der sich Schachteln jeder dieser Größen restlos füllen lassen. Gesucht ist also die kleinste positive Zahl, die durch jede ganze Zahl von lo bis hi teilbar ist, das kleinste gemeinsame Vielfache (kgV) dieser Zahlen.
Implementiere smallest_multiple(lo, hi).
Eingabe
lo: Die kleinste Schachtelgröße.
hi: Die größte Schachtelgröße.
Ausgabe
Gib die kleinste positive ganze Zahl zurück, die durch jede der Zahlen lo, lo + 1, ..., hi ohne Rest teilbar ist.
Einschränkungen
1 ≤ lo ≤ hi ≤ 40 (das Ergebnis passt in eine vorzeichenbehaftete 64-Bit-Ganzzahl)
Beispiele
Eingabe:
lo = 1
hi = 6
Erwartete Ausgabe:
expected = 60
Eingabe:
long long lo = 1;
long long hi = 6;
Erwartete Ausgabe:
long long expected = 60;
Eingabe:
long lo = 1;
long hi = 6;
Erwartete Ausgabe:
long expected = 60;
Erläuterung
60 ist durch 1, 2, 3, 4, 5 und 6 teilbar, und keine kleinere positive Zahl ist es, also lautet die Antwort 60.
Eingabe:
lo = 4
hi = 6
Erwartete Ausgabe:
expected = 60
Eingabe:
long long lo = 4;
long long hi = 6;
Erwartete Ausgabe:
long long expected = 60;
Eingabe:
long lo = 4;
long hi = 6;
Erwartete Ausgabe:
long expected = 60;
Erläuterung
kgV(4, 5) = 20 und kgV(20, 6) = 60, die Antwort ist also wieder 60. Die kleinen Größen ändern nichts.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Das kgV eines ganzen Bereichs lässt sich Zahl für Zahl aufbauen.
Hinweis 2
kgV(a, b) = a / ggT(a, b) × b.
Hinweis 3
Teile, bevor du multiplizierst, dann wird der Zwischenwert nie größer als das Ergebnis.
Erwartete Komplexität
Zeit O(n log M), zusätzlicher Speicher O(1)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.