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.

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 pytania3

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.