0Pricing
Coding Interview Prep · Lekcja

Szybkie potęgowanie modularne

Obliczanie potęg za pomocą pow(a, b, m)

Szybkie potęgowanie modularne to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 2 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.

Problem potęgowania

Często trzeba podnieść liczbę do ogromnej potęgi, wykonując wszystko modulo. Mnożenie kolejnych czynników po jednym wymagałoby zdecydowanie zbyt wielu kroków. ⚡

Podejście naiwne jest zbyt wolne

Pętla wykonująca mnożenie b razy działa w O(b) krokach. Przy wykładniku bliskim miliardowi przekroczy limit czasu, zanim w ogóle się zakończy.

for _ in range(b): r = r * a % MOD

Potęguj przez podnoszenie do kwadratu

Trik polega na podnoszeniu do kwadratu: a do potęgi 8 jest równe ((a do kwadratu) do kwadratu) do kwadratu. Każde podniesienie do kwadratu podwaja wykładnik, więc ogromne potęgi można osiągnąć w kilku krokach.

Odczytaj wykładnik binarnie

Każdy wykładnik jest sumą potęg liczby dwa, czyli ma swoją postać binarną. Dlatego mnoży się tylko przez potęgi bazowe odpowiadające ustawionym bitom, pomijając pozostałe.

# 13 = 1101 -> a^8 * a^4 * a^1

Sprawdź najmłodszy bit

Użyj b & 1, aby sprawdzić najmłodszy bit. Jeśli wynosi 1, należy uwzględnić bieżącą podstawę w dotychczasowym wyniku przed przejściem dalej.

if b & 1: result = result * base % MOD

Przesuwaj i podnoś do kwadratu w każdej rundzie

Po każdym bicie podnieś podstawę do kwadratu i przesuń wykładnik o jeden bit w prawo. Dla realistycznych danych pętla wykonuje tylko około 30–60 iteracji.

base = base * base % MOD
b >>= 1

Połącz wszystko

Ustaw wynik początkowy na 1, a następnie wykonuj pętlę, dopóki wykładnik jest dodatni. Cała ta idea szybkiego potęgowania jest również nazywana potęgowaniem binarnym lub potęgowaniem przez podnoszenie do kwadratu.

result = 1
while b > 0:
    if b & 1: result = result*base%MOD
    base = base*base%MOD
    b >>= 1

Działa w czasie logarytmicznym

Ponieważ każda runda zmniejsza wykładnik o połowę, koszt wynosi O(log b). Miliard mnożeń zostaje w ten sposób zastąpiony mniej więcej trzydziestoma, co mieści się w każdym limicie.

Python udostępnia pow

Rzadko trzeba pisać tę pętlę samodzielnie: wbudowana funkcja pow(a, b, m) w Pythonie wykonuje za Państwa szybkie potęgowanie modularne z prędkością kodu C.

print(pow(2, 100, MOD))

Dlaczego wkrótce będzie to ważne

Szybkie potęgowanie jest podstawą odwrotności modularnej wynikającej z twierdzenia Fermata, z którą spotkają się Państwo w następnej lekcji. Warto opanować je teraz, aby dzielenie modulo stało się proste.

Najpierw sprawdź podstawę

Przed rozpoczęciem pętli zredukuj podstawę za pomocą base % MOD. Podstawa większa od modułu bez tej operacji powiększałaby każdą kolejną operację podnoszenia do kwadratu.

base = a % MOD

Szybkie sprawdzenie

Jak szybkie jest szybkie potęgowanie modularne?

Podsumowanie

Można teraz podnosić liczby do ogromnych wykładników w czasie O(log b), podnosząc je do kwadratu i odczytując bity. W Pythonie wystarczy wywołać pow(a, b, m) i przejść dalej. 🚀

Często zadawane pytania

Czy lekcja „Szybkie potęgowanie modularne” jest bezpłatna?

Tak — pełny tekst „Szybkie potęgowanie modularne” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.

Co nauczysz się w „Szybkie potęgowanie modularne”?

Obliczanie potęg za pomocą pow(a, b, m) Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?

Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 2 z 4.

Ile czasu zajmuje lekcja „Szybkie potęgowanie modularne”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?

Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

  1. Działania modulo liczby pierwszej
  2. Szybkie potęgowanie modularne
  3. Odwrotność modularna z twierdzenia Fermata
  4. nCr z wcześniej obliczonymi silniami
← Powrót do Coding Interview Prep