Least Common Multiple

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

lcm(a, b) = a × b / gcd(a, b) , obliczone jako a / gcd(a, b) × b , aby żadna wartość pośrednia 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ść czasowa wynosi O(log(min(a, b))) , czyli tyle, ile kosztuje algorytm Euklidesa, a złożoność pamięciowa to O(1) . Przechodzenie przez wielokrotności większej liczby ma złożoność O(min(a, b)) , a zliczanie co jeden — O(lcm(a, b)) .

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 oraz lcm(12, 10) = 60 . Bieżąca wartość szybko rośnie, więc 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ą zarówno a, jak i b dzielą się bez reszty.

Funkcja

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

ainteger: pierwsza dodatnia liczba całkowita
binteger: druga dodatnia liczba całkowita
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.

Pytanie dodatkowe

Czy potrafisz znaleźć NWD bez użycia 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 są powiązane zależnością: gcd(a, b) × lcm(a, b) = a × b. Szybka odpowiedź to więc a × b / gcd(a, b). Iloczyn może osiągnąć wartość 10^12 i spowodować przepełnienie 32-bitowej liczby całkowitej, nawet gdy wynik się mieści, dlatego przed mnożeniem podziel przez NWD.

Odliczaj w górę od większej liczby

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

Intuicja

Odpowiedź jest co najmniej równa większej liczbie. Zacznij od m równego max(a, b) i dodawaj 1, aż obie liczby będą go dzielić; sprawdzasz kandydatów w kolejności rosnącej, więc pierwsze trafienie jest najmniejsze. Dla 4 i 6 sprawdzasz liczby od 6 do 11 i kończysz na 12. Pętla zawsze się kończy, ponieważ a × b jest wspólną wielokrotnością.

Liczba prób jest w przybliżeniu równa wielkości odpowiedzi. Dla liczb pierwszych 46337 i 46327 odpowiedź wynosi 2146654199, co oznacza ponad dwa miliardy prób.

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ź przez wielokrotności większej liczby

Intuicja

Odpowiedź musi być wielokrotnością większej liczby, big, więc sprawdzaj kolejne wartości big, 2 × big, 3 × big i zatrzymaj się na pierwszej, przez którą dzieli się mniejsza liczba. Dla 4 i 6 sprawdzasz 6, a potem 12.

Ponieważ small × big jest zawsze wspólną wielokrotnością, pętla wykona się co najwyżej min(a, b) razy, czyli w tym przypadku najwyżej milion razy. To wystarczająco szybko dla tych ograniczeń, ale liczba iteracji nadal rośnie wraz z danymi wejściowymi; dla liczb do 10^18 byłoby to już zbyt wolne.

Algorytm

Niech big oznacza 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. Dla każdej liczby pierwszej NWD przyjmuje mniejszą z jej dwóch potęg, a NWW większą, więc razem uwzględniają każdy czynnik liczby a i liczby b dokładnie raz: gcd × lcm = a × b. Dla 4 = 2² i 6 = 2 × 3 NWD wynosi 2, a NWW 2² × 3 = 12.

Algorytm Euklidesa znajduje NWD w O(log(min(a, b))) krokach. Następnie oblicz a / gcd × b w tej kolejności: NWD dzieli a bez reszty, więc nic nie tracimy, a żaden krok nie przekracza wyniku. a × b / gcd powoduje przepełnienie liczby 32-bitowej dla a = b = 10^6, gdy iloczyn wynosi 10^12, a wynik zaledwie 10^6.

Algorytm

Skopiuj a i b do x i y.
Gdy 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

Najpierw obliczanie a × b. W Javie, C, C++, C# i Rust iloczyn dwóch liczb bliskich 10^6 przekracza zakres 32-bitowej liczby całkowitej i daje błędny lub ujemny wynik (w kompilacji debug Rust powoduje panikę), mimo że NWW mieści się w tym zakresie.
Dzielenie w arytmetyce zmiennoprzecinkowej. Wynik może wynosić 2.146654199E9 albo stracić ostatnie cyfry; wykonuj wszystkie obliczenia na liczbach całkowitych.
Uruchamianie pętli Euklidesa bezpośrednio na a i b. Po jej zakończeniu zmienne te zawierają NWD i 0, więc operuj na kopiach.
Zakładanie, że wynikiem jest a × b. Tak jest tylko wtedy, gdy liczby nie mają wspólnego dzielnika większego od 1: lcm(4, 6) wynosi 12, a nie 24.

Najczęstsze pytania3

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

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

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

Przy użyciu wzoru na NWD złożoność czasowa wynosi O(log(min(a, b))), czyli tyle, ile kosztuje algorytm Euklidesa, a złożoność pamięciowa to O(1). Przechodzenie przez wielokrotności większej liczby ma złożoność O(min(a, b)), a zliczanie co jeden — O(lcm(a, b)).

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 oraz lcm(12, 10) = 60. Bieżąca wartość szybko rośnie, więc używaj liczb całkowitych 64-bitowych, gdy lista jest długa.