Szybkie potęgowanie modularne
Obliczanie potęg za pomocą pow(a, b, m)
Szybkie potęgowanie modularne to bezpłatna lekcja Competitive Programming Academy 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 Competitive Programming Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Competitive Programming Academy 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 % MODPotę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^1Sprawdź 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 % MODPrzesuwaj 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 >>= 1Połą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 >>= 1Dział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 % MODSzybkie 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 Competitive Programming Academy, przejdź na CoddyKit PRO. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Co nauczysz się w „Szybkie potęgowanie modularne”?
Obliczanie potęg za pomocą pow(a, b, m) Ćwiczysz Competitive Programming Academy 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ąć Competitive Programming Academy?
Nie wymagamy żadnego doświadczenia. Competitive Programming Academy 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 Competitive Programming Academy?
Tak. Każda lekcja Competitive Programming Academy 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
- Działania modulo liczby pierwszej
- Szybkie potęgowanie modularne
- Odwrotność modularna z twierdzenia Fermata
- nCr z wcześniej obliczonymi silniami