Greatest Common Divisor

Q: Jaka jest złożoność czasowa algorytmu Euklidesa?

Działa w O(log(min(a, b))) krokach, ponieważ co dwa kroki co najmniej o połowę zmniejsza większą liczbę. Najgorszy przypadek to para kolejnych liczb Fibonacciego. Dla liczb nie większych niż 10^9 oznacza to najwyżej 43 kroki, a algorytm używa dodatkowej pamięci O(1) .

Q: Dlaczego gcd(a, b) jest równe gcd(b, a % b)?

Zapisz a = q × b + r przy r = a % b . Liczba, która dzieli a i b , dzieli również a - q × b , czyli r . Liczba, która dzieli b i r , dzieli również q × b + r , czyli a . Obie pary mają te same wspólne dzielniki, więc mają też ten sam największy wspólny dzielnik.

PoczątkującyMatematyka i symulacja

+10

Otrzymujesz dwie dodatnie liczby całkowite a i b. Zwróć ich największy wspólny dzielnik: największą liczbę całkowitą, która dzieli obie liczby bez reszty.

Na przykład liczby, które dzielą zarówno 8, jak i 12, to 1, 2 i 4, więc odpowiedzią jest 4.

Funkcja

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

ainteger: pierwsza dodatnia liczba całkowita
binteger: druga dodatnia liczba całkowita
Zwracainteger: największa liczba całkowita, która dzieli zarówno a, jak i b

Ograniczenia

1 ≤ a ≤ 10⁹
1 ≤ b ≤ 10⁹

Przykłady

Wejście: a = 12b = 18
Wyjście: 6
Wyjaśnienie: Dzielnikami liczby 12 są 1, 2, 3, 4, 6 i 12; dzielnikami liczby 18 są 1, 2, 3, 6, 9 i 18. Największy wspólny dzielnik to 6.

Wejście: a = 17b = 5
Wyjście: 1
Wyjaśnienie: 17 i 5 są liczbami pierwszymi i różnymi, więc jedynym wspólnym dzielnikiem jest 1.

Wejście: a = 42b = 42
Wyjście: 42
Wyjaśnienie: Liczba dzieli samą siebie, a żadna liczba większa niż 42 nie może dzielić 42, więc największy wspólny dzielnik liczb 42 i 42 to 42.

+14 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Czy potrafisz rozszerzyć algorytm Euklidesa tak, aby zwracał również liczby całkowite x i y spełniające równanie a × x + b × y = gcd(a, b)?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Definicja sugeruje sprawdzanie kolejnych kandydatów jeden po drugim i sprawdza się to przy małych liczbach. Jednak gdy a i b są nie większe niż 10^9, dwie duże liczby, które nie mają wspólnego dzielnika, wymuszają miliard prób. Spostrzeżenie Euklidesa, że gcd(a, b) jest równe gcd(b, a % b), tak szybko zmniejsza liczby, że żadna para liczb nie większych niż 10^9 nie wymaga więcej niż 43 kroków.

Odliczaj w dół od mniejszej liczby

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

Intuicja

Żaden wspólny dzielnik nie może być większy od mniejszej z tych dwóch liczb, ponieważ dzielnik b jest co najwyżej równy b. Zacznij więc od kandydata d równego min(a, b) i zmniejszaj go o jeden, aż będzie dzielił obie liczby. Ponieważ sprawdzasz kandydatów od największego, pierwszy pasujący jest największy.

Dla 12 i 18 sprawdzasz 12 (nie dzieli 18), potem 11, 10, 9, 8 i 7, które nie pasują, a następnie zatrzymujesz się na 6. Pętla zawsze się kończy, ponieważ 1 dzieli każdą liczbę.

Koszt zależy od liczby kandydatów. Dla 999999937 i 999999929, dwóch liczb pierwszych, odpowiedź wynosi 1, a pętla wykonuje się prawie 10^9 razy. To zdecydowanie za wolno dla największych testów.

Algorytm

Ustaw d na mniejszą z wartości a i b.
Gdy a % d lub b % d nie jest równe 0, odejmij 1 od d.
Zwróć d.

def gcd(a, b):
    d = min(a, b)
    while a % d != 0 or b % d != 0:
        d -= 1
    return d

Algorytm Euklidesa

Intuicja

Zapisz a = q × b + r, gdzie r = a % b. Każda liczba, która dzieli zarówno a, jak i b, dzieli też r = a - q × b. Każda liczba, która dzieli zarówno b, jak i r, dzieli też a = q × b + r. Zatem pary (a, b) i (b, r) mają dokładnie te same wspólne dzielniki, a także ten sam największy wspólny dzielnik.

Zastąp (a, b) przez (b, a % b) i powtarzaj, aż b będzie równe 0. Każda liczba dzieli 0, więc gcd(a, 0) = a, a a jest wynikiem. Dla 12 i 18: (12, 18) zmienia się w (18, 12), potem w (12, 6), a następnie w (6, 0); wynikiem jest 6. Pierwszy krok sam zamienia liczby miejscami, gdy a jest mniejsze, więc nigdy nie musisz ich sortować.

Co dwa kroki większa liczba zmniejsza się co najmniej o połowę, więc pętla wykonuje się O(log(min(a, b))) razy. Najwolniejsze dane wejściowe to kolejne liczby Fibonacciego, takie jak 701408733 i 433494437, a nawet dla nich potrzeba tylko 42 kroków.

Algorytm

Dopóki b nie jest równe 0, oblicz r = a % b.
Ustaw a = b i b = r.
Gdy b osiągnie 0, zwróć a.

def gcd(a, b):
    # gcd(a, b) == gcd(b, a % b), and gcd(a, 0) == a.
    while b != 0:
        a, b = b, a % b
    return a

Pułapki i przypadki brzegowe

Algorytm jest krótki, więc błędy wynikają z aktualizacji i warunku zakończenia.

Aktualizacja w niewłaściwej kolejności. a = b, a następnie b = a % b oblicza b % b, co zawsze daje 0, i zwraca b. Najpierw zapisz resztę w zmiennej tymczasowej albo przypisz obie wartości jednocześnie.
Zwracanie b zamiast a po zakończeniu pętli. W tym momencie b wynosi 0.
Kończenie odliczania na 2 lub rozpoczynanie go od max(a, b). Pierwsze pomija pary względnie pierwsze, takie jak 17 i 5; drugie marnuje czas na kandydatów, którzy nie mogą dzielić mniejszej liczby.
Używanie wielokrotnego odejmowania zamiast reszty z dzielenia. gcd(10^9, 1) wymaga wtedy miliarda odejmowań; operator % wykonuje je wszystkie w jednym kroku.

Najczęstsze pytania4

Jaka jest złożoność czasowa algorytmu Euklidesa?

Działa w O(log(min(a, b))) krokach, ponieważ co dwa kroki co najmniej o połowę zmniejsza większą liczbę. Najgorszy przypadek to para kolejnych liczb Fibonacciego. Dla liczb nie większych niż 10^9 oznacza to najwyżej 43 kroki, a algorytm używa dodatkowej pamięci O(1).

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

Zapisz a = q × b + r przy r = a % b. Liczba, która dzieli a i b, dzieli również a - q × b, czyli r. Liczba, która dzieli b i r, dzieli również q × b + r, czyli a. Obie pary mają te same wspólne dzielniki, więc mają też ten sam największy wspólny dzielnik.

Jaka jest różnica między NWD a NWW?

Największy wspólny dzielnik to największa liczba, która dzieli obie liczby wejściowe; najmniejsza wspólna wielokrotność to najmniejsza liczba, przez którą dzielą obie liczby wejściowe. Są one powiązane zależnością gcd(a, b) × lcm(a, b) = a × b, więc gdy znasz już NWD, NWW wynosi a / gcd(a, b) × b.

Jaki jest NWD dwóch liczb względnie pierwszych?

Dwie liczby są względnie pierwsze, gdy ich największy wspólny dzielnik wynosi 1, co oznacza, że nie mają wspólnego dzielnika pierwszego. Dwie różne liczby pierwsze są zawsze względnie pierwsze, podobnie jak dowolne dwie kolejne liczby całkowite, takie jak 8 i 9.