Least Common Multiple

Q: Jaki jest wzór na NWW dwóch liczb?

lcm(a, b) = a × b / gcd(a, b) , obliczane jako a / gcd(a, b) × b , aby wartość pośrednia nigdy nie przekraczała wyniku. Dla 4 i 6 NWD wynosi 2 , a 4 / 2 × 6 = 12 .

Q: Jaka jest złożoność czasowa obliczania NWW?

Przy użyciu wzoru na NWD złożoność wynosi O(log(min(a, b))) , czyli tyle, ile kosztuje algorytm Euklidesa, plus jedno dzielenie i jedno mnożenie. Wymaga dodatkowej pamięci O(1) . Przeszukiwanie wielokrotności jest znacznie wolniejsze: O(min(a, b)) , gdy zwiększasz wartość o większą liczbę, oraz O(lcm(a, b)) , gdy liczysz co jeden.

Q: Jak znaleźć NWW więcej niż dwóch liczb?

Składaj listę: lcm(a, b, c) = lcm(lcm(a, b), c) . Dla [4, 6, 10] , lcm(4, 6) = 12 i lcm(12, 10) = 60 . Bieżąca wartość szybko rośnie, więc uważaj na przepełnienie i używaj liczb całkowitych 64-bitowych, gdy lista jest długa.

PoczątkującyMatematyka i symulacja

+10

Otrzymujesz dwie dodatnie liczby całkowite a i b. Zwróć ich najmniejszą wspólną wielokrotność: najmniejszą dodatnią liczbę całkowitą, przez którą a i b dzielą się bez reszty.

Na przykład wielokrotnościami 6 są 6, 12, 18, 24 i tak dalej, wielokrotnościami 8 są 8, 16, 24 i tak dalej, a pierwszą liczbą na obu listach jest 24.

Funkcja

lcm(a: integer, b: integer) → integer

ainteger: pierwsza dodatnia liczba całkowita
binteger: druga liczba całkowita dodatnia
Zwracainteger: najmniejsza dodatnia liczba całkowita, która jest wielokrotnością zarówno a, jak i b

Ograniczenia

1 ≤ a ≤ 10⁶
1 ≤ b ≤ 10⁶
Wynik mieści się w 32-bitowej liczbie całkowitej ze znakiem: lcm(a, b) ≤ 2³¹-1. Iloczyn a × b może się nie mieścić.

Przykłady

Wejście: a = 4b = 6
Wyjście: 12
Wyjaśnienie: Wielokrotności 6 zaczynają się od 6, 12, 18; wielokrotności 4 zaczynają się od 4, 8, 12. Pierwszą liczbą na obu listach jest 12.

Wejście: a = 7b = 3
Wyjście: 21
Wyjaśnienie: 7 i 3 nie mają wspólnego dzielnika poza 1, więc ich najmniejsza wspólna wielokrotność jest ich iloczynem, czyli 21.

Wejście: a = 15b = 45
Wyjście: 45
Wyjaśnienie: 15 dzieli 45 bez reszty, więc 45 jest już wielokrotnością obu liczb i nie istnieje mniejsza wielokrotność 45.

+15 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Czy potrafisz znaleźć NWD bez używania dzielenia ani reszty z dzielenia, korzystając wyłącznie z odejmowania i dzielenia przez 2?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Najmniejsza wspólna wielokrotność i największy wspólny dzielnik to dwie strony tego samego faktu: gcd(a, b) × lcm(a, b) = a × b. Szybka odpowiedź to więc a × b / gcd(a, b), ale jest jeden haczyk. Iloczyn może osiągnąć wartość 10^12, która powoduje przepełnienie liczby 32-bitowej, nawet gdy wynik mieści się w jej zakresie, dlatego przed mnożeniem dzielisz przez NWD.

Odliczaj w górę od większej liczby

Poprawne, ale nie kończy się na największych testach

Intuicja

Odpowiedź jest wielokrotnością obu liczb, więc jest co najmniej tak duża jak większa z nich. Ustaw kandydata m na max(a, b) i dodawaj 1, aż zarówno a, jak i b będą go dzielić. Sprawdzasz kandydatów w rosnącej kolejności, więc pierwsza pasująca liczba jest najmniejsza.

Dla 4 i 6 sprawdzasz kolejno 6, 7, 8, 9, 10 i 11 — te liczby nie pasują — a następnie zatrzymujesz się na 12. Pętla zawsze się kończy, ponieważ a × b jest wspólną wielokrotnością.

Liczba prób jest zbliżona do wielkości odpowiedzi. Dla 46337 i 46327, które są liczbami pierwszymi, odpowiedzią jest 2146654199, więc pętla wykonuje się ponad dwa miliardy razy. To zdecydowanie za wolno.

Algorytm

Ustaw m na większą z wartości a i b.
Gdy m % a lub m % b nie jest równe 0, zwiększ m o 1.
Zwróć m.

def lcm(a, b):
    m = max(a, b)
    while m % a != 0 or m % b != 0:
        m += 1
    return m

Przechodź kolejno przez wielokrotności większej liczby

Intuicja

Większość kandydatów w tym zakresie nie ma szans: odpowiedź musi być wielokrotnością większej liczby, nazwijmy ją big. Przeskakuj więc od razu od jednej wielokrotności big do następnej: big, 2 × big, 3 × big i zatrzymaj się na pierwszej, przez którą dzieli się mniejsza liczba.

Dla 4 i 6 próbujesz 6 (4 nie dzieli tej liczby), a potem 12 (dzieli ją). Odpowiedź ma postać k × big dla pewnego k, a k jest nie większe od mniejszej liczby, ponieważ small × big zawsze jest wspólną wielokrotnością. Pętla wykonuje się więc najwyżej min(a, b) razy, czyli w tym przypadku nigdy więcej niż milion razy.

W tym przypadku to wystarczająco szybkie, ale czas działania nadal rośnie wraz z danymi wejściowymi. Przy liczbach do 10^18 tak by nie było.

Algorytm

Niech big będzie większą liczbą, a small mniejszą.
Ustaw m = big.
Gdy m % small nie jest równe 0, dodawaj big do m.
Zwróć m.

def lcm(a, b):
    big, small = max(a, b), min(a, b)
    m = big
    while m % small != 0:
        m += big
    return m

Podziel przez NWD, a następnie pomnóż

Intuicja

Rozłóż obie liczby na czynniki pierwsze. NWD bierze każdy czynnik pierwszy z mniejszą z jego dwóch potęg, a NWW bierze większą potęgę; razem wykorzystują każdy czynnik liczby a i liczby b dokładnie raz. Otrzymujemy więc gcd(a, b) × lcm(a, b) = a × b, a zatem lcm(a, b) = a × b / gcd(a, b). Dla 4 = 2² i 6 = 2 × 3 NWD wynosi 2, a NWW wynosi 2² × 3 = 12.

Znajdź NWD algorytmem Euklidesa: zastępuj (x, y) przez (y, x % y), aż y będzie równe 0. Zajmuje to O(log(min(a, b))) kroków.

Następnie oblicz a / gcd × b, w tej kolejności. NWD dzieli a bez reszty, więc dzielenie niczego nie gubi, a wynik nigdy nie przekracza szukanej wartości. Zapisanie zamiast tego a × b / gcd powoduje przepełnienie 32-bitowej liczby całkowitej dla a = b = 10^6: iloczyn wynosi 10^12, podczas gdy wynik to tylko 10^6.

Algorytm

Skopiuj a i b do x i y.
Dopóki y nie jest równe 0, zastąp (x, y) przez (y, x % y). Teraz x jest NWD.
Podziel a przez x.
Pomnóż wynik przez b i zwróć go.

def lcm(a, b):
    x, y = a, b
    while y != 0:
        x, y = y, x % y
    # x is gcd(a, b). Divide before multiplying.
    return a // x * b

Pułapki i przypadki brzegowe

Wzór mieści się w jednym wierszu, a błędy wynikają z kolejności działań arytmetycznych.

Najpierw obliczanie a × b. W Java, C, C++, C# i Rust iloczyn dwóch liczb bliskich 10^6 przepełnia 32-bitową liczbę całkowitą, a wynik jest niepoprawny lub ujemny (zamiast tego kompilacja debugująca w Rust powoduje panic), mimo że prawdziwa wartość NWW mieści się w tym zakresie.
Dzielenie a × b przez NWD w arytmetyce zmiennoprzecinkowej. Wynik może mieć postać 2.146654199E9 albo stracić ostatnie cyfry; wykonuj wszystkie działania na liczbach całkowitych.
Uruchamianie pętli Euklidesa bezpośrednio na a i b, a następnie używanie ich we wzorze. Po zakończeniu pętli zawierają one NWD i 0, więc pracuj na kopiach.
Zakładanie, że wynik to a × b. Jest tak tylko wtedy, gdy te dwie liczby nie mają wspólnych czynników: lcm(4, 6) to 12, a nie 24.

Najczęstsze pytania4

Jaki jest wzór na NWW dwóch liczb?

lcm(a, b) = a × b / gcd(a, b), obliczane jako a / gcd(a, b) × b, aby wartość pośrednia nigdy nie przekraczała wyniku. Dla 4 i 6 NWD wynosi 2, a 4 / 2 × 6 = 12.

Dlaczego gcd(a, b) × lcm(a, b) jest równe a × b?

Dla każdej liczby pierwszej NWD wykorzystuje mniejszą z jej potęg w a i b, a NWW — większą. Mniejsza plus większa to suma obu potęg, która jest dokładnie potęgą tej liczby pierwszej w a × b. Każda liczba pierwsza się zgadza, więc oba iloczyny są równe.

Jaka jest złożoność czasowa obliczania NWW?

Przy użyciu wzoru na NWD złożoność wynosi O(log(min(a, b))), czyli tyle, ile kosztuje algorytm Euklidesa, plus jedno dzielenie i jedno mnożenie. Wymaga dodatkowej pamięci O(1). Przeszukiwanie wielokrotności jest znacznie wolniejsze: O(min(a, b)), gdy zwiększasz wartość o większą liczbę, oraz O(lcm(a, b)), gdy liczysz co jeden.

Jak znaleźć NWW więcej niż dwóch liczb?

Składaj listę: lcm(a, b, c) = lcm(lcm(a, b), c). Dla [4, 6, 10], lcm(4, 6) = 12 i lcm(12, 10) = 60. Bieżąca wartość szybko rośnie, więc uważaj na przepełnienie i używaj liczb całkowitych 64-bitowych, gdy lista jest długa.