Działania modulo liczby pierwszej
Dodawanie i mnożenie z pozostawaniem w obrębie modułu
Działania modulo liczby pierwszej to bezpłatna lekcja Competitive Programming Academy na CoddyKit. To lekcja 1 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.
Dlaczego stosować modulo
Wyniki w zadaniach konkursowych mogą stać się ogromne, znacznie przekraczając zakres dowolnego typu całkowitego. Dlatego zadania proszą o wynik modulo dużej liczby pierwszej, aby utrzymać małe wartości. 🔢
Poznaj słynny moduł
Liczbą pierwszą, którą zobaczą Państwo najczęściej, jest 1000000007, często zapisywana jako 1e9+7. Jest wystarczająco duża, aby unikać kolizji, i wystarczająco mała, aby zmieścić się w 64 bitach.
MOD = 1000000007Co oznacza modulo
Operator modulo zwraca resztę z dzielenia. Zatem 17 % 5 wynosi 2, ponieważ przy dzieleniu 17 przez 5 pozostaje reszta 2.
print(17 % 5) # 2Dodawanie pozostaje w zakresie
Można najpierw dodać wartości i zastosować modulo na końcu albo stosować modulo na bieżąco. Reszta będzie taka sama, więc warto często redukować wartości, aby zachować ich mały rozmiar.
total = (a + b) % MODMnożenie również pozostaje w zakresie
Ta sama zasada dotyczy mnożenia: należy obliczyć iloczyn modulo liczby pierwszej. Python natywnie obsługuje duże liczby całkowite, ale stosowanie modulo utrzymuje każdą wartość małą i przyspiesza obliczenia.
prod = (a * b) % MODRedukuj po każdym kroku
W długiej pętli należy stosować % MOD w każdej iteracji. Zapobiega to nadmiernemu wzrostowi liczb i utrzymuje każdą operację tanią oraz przewidywalną.
ans = (ans * i) % MODOdejmowanie może dać wynik ujemny
Odejmowanie może w wielu językach dać ujemną resztę. Przed zastosowaniem końcowego modulo należy dodać MOD, aby wynik znalazł się w bezpiecznym zakresie od 0.
diff = (a - b + MOD) % MODPrzyjazne modulo w Pythonie
Dobra wiadomość: operator % w Pythonie już zwraca wynik nieujemny dla dodatniego modułu. Dlatego -1 % 7 daje 6, a nie -1, co eliminuje potrzebę dodatkowej korekty.
print(-1 % 7) # 6Modulo rozdziela się na operacje
Najważniejsza idea: (a op b) % m jest równe (a%m op b%m) % m dla dodawania i mnożenia. Dzięki temu można zredukować argumenty przed ich połączeniem.
Dzielenie jest wyjątkiem
Dodawanie, odejmowanie i mnożenie działają poprawnie modulo. Zwykłe dzielenie już nie, dlatego w dalszej części kursu potrzebna będzie odwrotność modularna.
Ustaw MOD raz na początku
Zdefiniuj MOD jako stałą na początku rozwiązania. Jedna nazwana wartość jest lepsza niż wielokrotne wpisywanie 1000000007 w kodzie, gdzie łatwo przeoczyć literówkę.
MOD = 10**9 + 7Szybkie sprawdzenie
Dlaczego przed zastosowaniem modulo do odejmowania należy dodać MOD?
Podsumowanie
Można teraz utrzymywać ogromne wartości w małym zakresie za pomocą modułu pierwszego, takiego jak 1e9+7. Należy redukować dodawanie, odejmowanie i mnożenie po każdym kroku, pamiętać o liczbach ujemnych, a dzielenie wykonywać za pomocą odwrotności. 🎯
Często zadawane pytania
Czy lekcja „Działania modulo liczby pierwszej” jest bezpłatna?
Tak — pełny tekst „Działania modulo liczby pierwszej” 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 „Działania modulo liczby pierwszej”?
Dodawanie i mnożenie z pozostawaniem w obrębie modułu Ć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 1 z 4.
Ile czasu zajmuje lekcja „Działania modulo liczby pierwszej”?
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