Co już umiesz i czego się nauczysz
Ta lekcja zakłada, że przerobiłeś lekcje Typy zmiennych, Input / Output, If / Else, While loop i For loop. Operator % pojawił się w nich już kilka razy: w lekcji o typach liczyłeś 17 % 5 i wyciągałeś ostatnią cyfrę przez n % 10, w lekcji o if sprawdzałeś parzystość i poznałeś pułapkę -7 % 2, a w lekcjach o pętlach rozbierałeś liczby na cyfry i liczyłeś NWD algorytmem Euklidesa.
Teraz zbierzemy to wszystko w jednym miejscu i pójdziemy dużo dalej. Modulo to jedno z najczęściej używanych narzędzi w zadaniach olimpijskich: pojawia się wszędzie tam, gdzie coś się powtarza w kółko (godziny, dni, pozycje w kółeczku), gdzie trzeba sprawdzić podzielność, rozłożyć liczbę na części — i tam, gdzie wynik jest tak ogromny, że zadanie każe wypisać tylko jego resztę.
Uczymy się tak samo jak poprzednio: przepisuj przykłady do swojego edytora i uruchamiaj je, przy pytaniach „Co wypisze program?” najpierw licz w głowie albo na kartce, a dopiero potem sprawdzaj odpowiedź, i po każdej części rób ćwiczenia w sprawdzarce. Nie przerabiaj wszystkiego za jednym razem — rób przerwy po kolejnych częściach.
Reszta i podzielność
Iloraz i reszta, reszty idące w kółko, kolejność działań, podzielność i wielokrotności.
Rozkładanie liczb
Czas i pieniądze na jednostki, dowolna cyfra liczby, inne systemy liczbowe.
W kółko i pod kreskę
Zegar, dni tygodnia, numeracja od 1, chodzenie po kółku — i pułapki z liczbami ujemnymi.
Modulo na olimpiadzie
Wynik modulo 10⁹ + 7, reszta z olbrzyma, NWD, dzielenie pisemne i szybkie potęgowanie.
cout << x << " " w pętli niczego nie psuje. Uważaj natomiast na spacje i znaki w środku wiersza, na zera z przodu (05, a nie 5) i na wielkość liter.
Mapa lekcji
Reszta z dzielenia, czyli %
Zacznijmy od czegoś, co znasz z podstawówki. Masz 17 cukierków i pakujesz je do torebek po 5 sztuk. Ile torebek zapełnisz i ile cukierków zostanie luzem? Pełne będą 3 torebki (bo 3 · 5 = 15), a luzem zostaną 2 cukierki. W szkole zapisuje się to jako 17 : 5 = 3 reszty 2.
W C++ te dwie liczby liczy się dwoma różnymi operatorami. Ukośnik / daje iloraz: ile razy dzielnik mieści się w liczbie, czyli ile jest pełnych torebek. Procent % daje resztę: ile zostało, czyli ile cukierków jest luzem. Znak % czytamy „modulo”, a całe 17 % 5 — „siedemnaście modulo pięć”.
int a = 17, b = 5;
cout << a / b << "\n"; // ile pełnych torebek
cout << a % b << "\n"; // ile cukierków zostaje luzem
Oba operatory działają na liczbach całkowitych: int i long long. Pamiętasz z lekcji o typach, że dzielenie / dwóch liczb całkowitych nie daje ułamka — 17 / 5 to 3, a nie 3,4.
To, co dzielenie „ucięło”, wcale nie znika. Właśnie to jest reszta, którą zwraca %. Dlatego / i % prawie zawsze chodzą w parze.
Sprawdzenie: a = b · q + r
Iloraz i reszta pasują do siebie jak dwa kawałki puzzli. Jeśli q = a / b i r = a % b, to zawsze a = b · q + r. Pełne torebki razy ich pojemność plus cukierki luzem dają z powrotem wszystkie cukierki: 5 · 3 + 2 = 17. Taki zapis to świetny sposób, żeby sprawdzić, czy dobrze liczysz. Oto program, który wypisuje go dla dowolnych liczb:
int a, b;
cin >> a >> b;
int q = a / b; // iloraz
int r = a % b; // reszta
cout << a << " = " << b << " * " << q << " + " << r << "\n";
Przyjrzyj się kilku dzieleniom naraz. Każdy wiersz tabeli warto sprawdzić w głowie:
| a | b | a / b | a % b | sprawdzenie b · q + r |
|---|---|---|---|---|
| 17 | 5 | 3 | 2 | 5 · 3 + 2 = 17 |
| 20 | 5 | 4 | 0 | 5 · 4 + 0 = 20 — dzieli się bez reszty |
| 3 | 5 | 0 | 3 | 5 · 0 + 3 = 3 — piątka nie mieści się ani razu |
| 0 | 5 | 0 | 0 | 5 · 0 + 0 = 0 — nie ma czego dzielić |
| 5 | 5 | 1 | 0 | 5 · 1 + 0 = 5 — jedna pełna torebka |
| 99 | 10 | 9 | 9 | 10 · 9 + 9 = 99 |
| 100 | 7 | 14 | 2 | 7 · 14 + 2 = 100 |
| 1000 | 3 | 333 | 1 | 3 · 333 + 1 = 1000 |
Zwróć uwagę na trzeci wiersz: gdy liczba jest mniejsza od dzielnika, iloraz to 0, a reszta to cała liczba. Trzech cukierków nie da się zapakować do torebki na pięć — wszystkie zostają luzem. To częsta pułapka w pytaniach typu „co wypisze program”: 3 % 5 to 3, a nie 0 ani 2.
Reszta jest zawsze mniejsza od dzielnika
To najważniejsza własność reszty: a % b jest zawsze liczbą od 0 do b − 1 (dla nieujemnego a i dodatniego b — liczbami ujemnymi zajmiemy się w części 6). Dlaczego? Gdyby luzem zostało 5 cukierków albo więcej, dałoby się z nich zapakować jeszcze jedną pełną torebkę. Stąd wiesz od razu, jakie wyniki może dać modulo:
| wyrażenie | możliwe wyniki |
|---|---|
x % 2 | 0 albo 1 — parzysta albo nieparzysta |
x % 10 | od 0 do 9 — ostatnia cyfra liczby |
x % 7 | od 0 do 6 — jak siedem dni tygodnia |
x % 24 | od 0 do 23 — jak godziny na zegarze |
x % 60 | od 0 do 59 — jak minuty i sekundy |
x % 1 | zawsze 0 — jedynka mieści się w każdej liczbie |
Reszty chodzą w kółko
Zobaczmy, co dzieje się z ilorazem i resztą, gdy dzielona liczba rośnie o 1. Ten program wypisuje tabelkę dla liczb od 0 do 9 przy dzieleniu przez 4 (kolumny wyrównuje setw z lekcji o wejściu i wyjściu):
cout << " a a/4 a%4\n";
for (int a = 0; a <= 9; a++) {
cout << setw(2) << a << setw(4) << a / 4 << setw(4) << a % 4 << "\n";
}
Reszta rośnie razem z liczbą: 0, 1, 2, 3 — ale gdy miałaby dojść do 4, w liczbie mieści się kolejna pełna czwórka. Iloraz rośnie wtedy o 1, a reszta spada z powrotem do 0.
I tak w kółko: 0, 1, 2, 3, 0, 1, 2, 3, 0… Reszta nigdy nie dochodzi do dzielnika — po b − 1 zawsze wraca zero.
To obserwacja, na której opiera się cała część 5: zegary, dni tygodnia i chodzenie po kółku działają dokładnie tak samo.
Kolejność działań
Operator % ma ten sam priorytet co * i /. W wyrażeniu najpierw liczone są *, / i % — po kolei od lewej do prawej, w takiej kolejności, w jakiej stoją — a dopiero potem + i -. Zobacz, jak bardzo nawias zmienia wynik:
cout << 2 + 7 % 3 << "\n"; // 2 + (7 % 3) = 2 + 1
cout << (2 + 7) % 3 << "\n"; // 9 % 3
cout << 20 % 6 * 2 << "\n"; // (20 % 6) * 2 = 2 * 2
cout << 20 % (6 * 2) << "\n"; // 20 % 12
cout << 100 - 17 % 5 << "\n"; // 100 - 2
% ma pierwszeństwo przed + i -, a z * i / jest na równi — wtedy decyduje kolejność od lewej do prawej. Jeśli nie jesteś pewien, co policzy się najpierw, wstaw nawias. Nawias nigdy nie zaszkodzi, a często ratuje przed błędem.
Operator %=
Tak jak x += 5 to skrót od x = x + 5, tak x %= 10 to skrót od x = x % 10: zastąp x jego resztą z dzielenia przez 10. Przyda się, gdy liczba ma „zostać tylko resztą”.
int x = 1234;
x %= 100; // x = x % 100
cout << x << "\n";
x %= 7; // 34 % 7
cout << x << "\n";
1234 % 100 to dwie ostatnie cyfry, czyli 34. Potem 34 % 7: siódemka mieści się w 34 cztery razy (28), zostaje 6.
Jeszcze jedno na start: % działa wyłącznie na liczbach całkowitych. Z typem double program się nie skompiluje — zobaczysz to w części 6.
Najpierw odpowiedz w myślach — prześledź program obrót po obrocie — a dopiero potem kliknij „Pokaż odpowiedź”.
cout << 23 % 4;
Pokaż odpowiedź
cout << 4 % 23;
Pokaż odpowiedź
cout << 50 / 7 << " " << 50 % 7;
Pokaż odpowiedź
cout << 10 - 10 % 4 * 2;
Pokaż odpowiedź
int x = 47;
x %= 10;
x %= 4;
cout << x;
Pokaż odpowiedź
for (int i = 1; i <= 8; i++) {
cout << i % 3;
}
Pokaż odpowiedź
cout << 1000000 % 1000 << " " << 999999 % 1000;
Pokaż odpowiedź
7 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
Czy się dzieli? Sprawdź, czy reszta to zero
Liczba a dzieli się przez b (bez reszty), gdy przy dzieleniu nic nie zostaje — czyli dokładnie wtedy, gdy a % b == 0. To jedno porównanie zobaczysz w programach olimpijskich setki razy. 36 dzieli się przez 4, bo 36 % 4 to 0. 36 nie dzieli się przez 5, bo 36 % 5 to 1.
int a, b;
cin >> a >> b;
if (a % b == 0) {
cout << a << " dzieli sie przez " << b << "\n";
} else {
cout << a << " nie dzieli sie przez " << b << ", reszta " << a % b << "\n";
}
W warunku if stoi porównanie a % b == 0 — z dwoma znakami równości, bo pytamy, czy reszta jest równa zeru (pojedyncze = to przypisanie, pamiętasz z lekcji o if).
Zamiast a % b != 0 można też pisać po prostu a % b — liczba różna od zera to w warunku prawda. Ale wersja z == 0 i != 0 jest czytelniejsza, więc jej się trzymamy.
Parzystość — dzielenie przez 2
Najczęstszy przypadek to dzielenie przez 2. Liczba jest parzysta, gdy x % 2 == 0. Z lekcji o if pamiętasz pułapkę: dla liczb ujemnych reszta bywa ujemna (-7 % 2 to −1), więc nieparzystość sprawdzaj przez x % 2 != 0 albo przez else — a nie przez x % 2 == 1.
int n;
cin >> n;
int parzyste = 0, nieparzyste = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (x % 2 == 0) {
parzyste++;
} else {
nieparzyste++;
}
}
cout << parzyste << " " << nieparzyste << "\n";
Parzyste są 4, −2 i 0. Zero jest parzyste: 0 % 2 to 0. Liczba −2 też: -2 % 2 to 0 — zero nie ma znaku.
A −9? -9 % 2 to −1, czyli nie zero, więc trafia do else — i dobrze, bo jest nieparzysta. Gdybyśmy zamiast else napisali if (x % 2 == 1), liczba −9 nie zostałaby policzona nigdzie.
Kto przez kogo? Dzielnik i wielokrotność
Uważaj na kolejność liczb przy %. Zdania „12 dzieli się przez 3”, „12 jest wielokrotnością 3” i „3 jest dzielnikiem 12” mówią to samo — i wszystkie zapisujemy jako 12 % 3 == 0. Liczba, którą dzielimy, zawsze stoi po lewej stronie %. Gdy napiszesz to odwrotnie, 3 % 12 da 3 i program uzna, że się nie dzieli.
| zdanie | warunek w C++ |
|---|---|
| a dzieli się przez b | a % b == 0 |
| a jest wielokrotnością b | a % b == 0 |
| b jest dzielnikiem a | a % b == 0 |
| a jest dzielnikiem b (a dzieli b) | b % a == 0 |
| a jest parzysta | a % 2 == 0 |
| a jest nieparzysta | a % 2 != 0 |
| a kończy się zerem | a % 10 == 0 |
Wielokrotności — pętlą i wzorem
Wypiszmy wszystkie liczby od 1 do n, które dzielą się przez k, i policzmy je. Pierwszy pomysł to pętla z if-em w środku:
int n, k;
cin >> n >> k;
int ile = 0;
for (int i = 1; i <= n; i++) {
if (i % k == 0) {
cout << i << " ";
ile++;
}
}
cout << "\nrazem: " << ile << "\n";
Liczbę ile da się jednak policzyć bez żadnej pętli. Wielokrotności k to k, 2k, 3k, … i żadna nie może przekroczyć n. Ile ich jest? Tyle, ile razy k mieści się w n — czyli dokładnie n / k.
Dla n = 20 i k = 6: 20 / 6 to 3 (6, 12 i 18). Kolejna wielokrotność, 24, już się nie mieści.
A ile wielokrotności k leży w przedziale od a do b? Policz te, które są nie większe od b, i odejmij te, które są mniejsze od a — czyli nie większe od a − 1: b / k − (a − 1) / k. Taki wzór działa w ułamku sekundy nawet dla liczb rzędu 10¹⁸, gdzie pętla nie miałaby żadnych szans:
long long a, b, k;
cin >> a >> b >> k;
cout << b / k - (a - 1) / k << "\n";
Sprawdźmy pierwszy przykład ręcznie. Do 40 jest 40 / 7 = 5 wielokrotności siódemki: 7, 14, 21, 28, 35. Do 9 jest ich 9 / 7 = 1: tylko 7. Różnica 5 − 1 = 4 to liczby 14, 21, 28 i 35 — dokładnie te z przedziału.
W drugim przykładzie pętla po trylionie liczb trwałaby setki lat. Wzór liczy wynik od razu.
Co k-ty raz — nowy wiersz co k liczb
Warunek i % k == 0 w pętli jest prawdziwy co k-ty obrót: dla i = k, 2k, 3k, … Dzięki temu łatwo zrobić coś „co k razy” — na przykład przejść do nowego wiersza po każdych pięciu wypisanych liczbach:
int n = 14, k = 5;
for (int i = 1; i <= n; i++) {
cout << i << " ";
if (i % k == 0) {
cout << "\n"; // po każdej k-tej liczbie nowy wiersz
}
}
Ten schemat przydaje się wszędzie, gdzie coś dzieje się cyklicznie: co trzeci klient dostaje rabat, co dziesiąty obrót pętli wypisujemy postęp, co siódmy dzień jest niedziela.
Zauważ, że "\n" wypisujemy po liczbie, a nie przed nią — dzięki temu nowy wiersz pojawia się dokładnie po 5, 10, 15…
Dwa warunki naraz
Liczba podzielna przez 3 i przez 5 to liczba podzielna przez 15 — to prawda. Ale uwaga: liczba podzielna przez 4 i przez 6 nie musi dzielić się przez 24. Wystarczy, że dzieli się przez 12 — najmniejszą wspólną wielokrotność 4 i 6 (NWW, wrócimy do niej w części 8). Sprawdźmy:
for (int i = 1; i <= 50; i++) {
if (i % 4 == 0 && i % 6 == 0) {
cout << i << " ";
}
}
cout << "\n";
12 i 36 nie dzielą się przez 24, a mimo to dzielą się i przez 4, i przez 6. Wniosek: gdy w zadaniu są dwa warunki podzielności, pisz oba połączone przez && — i nie zamieniaj ich „na oko” jednym.
Lata przestępne
Klasyczny przykład kilku warunków podzielności naraz. Rok jest przestępny (luty ma 29 dni), gdy dzieli się przez 4, ale nie dzieli się przez 100 — chyba że dzieli się przez 400, wtedy też jest przestępny. Dlatego 2024 był przestępny, 1900 nie był, a 2000 — był.
for (int r = 1896; r <= 1912; r++) {
if ((r % 4 == 0 && r % 100 != 0) || r % 400 == 0) {
cout << r << " ";
}
}
cout << "\n";
Rok 1900 dzieli się przez 4, ale też przez 100 — a przez 400 już nie. Dlatego nie jest przestępny i między 1896 a 1904 minęło aż 8 lat bez 29 lutego.
Nawiasy wokół && nie są tu konieczne (&& i tak liczy się przed ||), ale pokazują, jak czytać warunek.
Cecha podzielności — gdy liczba jest za duża
Czasem liczba ma tysiąc cyfr i nie mieści się w żadnym typie. Wtedy pomagają cechy podzielności ze szkoły: liczba dzieli się przez 3 (albo przez 9), gdy suma jej cyfr dzieli się przez 3 (albo przez 9). O podzielności przez 2, 5 i 10 decyduje ostatnia cyfra, a przez 4 i 25 — dwie ostatnie. Taką liczbę wczytujesz jako napis i liczysz na jej cyfrach:
string s;
cin >> s;
int suma = 0;
for (char c : s) {
suma += c - '0'; // znak cyfry zamieniony na liczbę
}
cout << "suma cyfr: " << suma << "\n";
if (suma % 3 == 0) {
cout << "dzieli sie przez 3\n";
} else {
cout << "nie dzieli sie przez 3\n";
}
Ta liczba ma 27 cyfr — nie zmieściłaby się nawet w long long. Ale żeby sprawdzić podzielność przez 3, wcale nie musimy jej mieć jako liczby: wystarczy suma cyfr, 135, a ta jest już malutka.
c - '0' zamienia znak cyfry na jej wartość — pamiętasz kody ASCII z lekcji o typach. W części 7 poznasz sposób, który działa dla dowolnego dzielnika, nie tylko dla 3 i 9.
Najpierw odpowiedz w myślach — prześledź program obrót po obrocie — a dopiero potem kliknij „Pokaż odpowiedź”.
cout << (91 % 7 == 0);
Pokaż odpowiedź
int ile = 0;
for (int i = 1; i <= 30; i++) {
if (i % 4 == 0) {
ile++;
}
}
cout << ile;
Pokaż odpowiedź
if (12 % 8 == 0 && 12 % 3 == 0) {
cout << "A";
} else {
cout << "B";
}
Pokaż odpowiedź
int r = 2100;
cout << ((r % 4 == 0 && r % 100 != 0) || r % 400 == 0);
Pokaż odpowiedź
cout << 100 / 7 - 49 / 7;
Pokaż odpowiedź
for (int i = 1; i <= 7; i++) {
cout << i;
if (i % 3 == 0) {
cout << "|";
}
}
Pokaż odpowiedź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
Rozkładanie na jednostki
W wielu zadaniach dane przychodzą w najmniejszej jednostce — w sekundach, groszach, centymetrach — a wynik trzeba podać w większych: w godzinach i minutach, w złotych i groszach. To robota dla pary / i %. Dzielenie mówi, ile jest pełnych większych jednostek, a modulo — ile zostało drobnych. Dokładnie jak torebki i cukierki z części 1: pełna godzina to „torebka” na 60 minut.
Minuty na godziny
int t;
cin >> t; // czas w minutach
cout << t / 60 << " h " << t % 60 << " min\n";
Godzina ma 60 minut, więc t / 60 to pełne godziny, a t % 60 — minuty, które nie złożyły się już na pełną godzinę. 135 = 2 · 60 + 15.
Dla 59 minut iloraz wynosi 0: nie ma ani jednej pełnej godziny, wszystkie 59 minut to reszta.
Sekundy na godziny, minuty i sekundy
Przy trzech jednostkach są dwa sposoby. Pierwszy: każdą jednostkę liczysz „z góry”, od całej liczby sekund. Drugi: odcinasz jednostki po kolei od najmniejszej — tak jak cyfry liczby w lekcji o while. Oba dają to samo; wybierz ten, który lepiej rozumiesz.
int s;
cin >> s;
int g = s / 3600; // 3600 s = 1 h
int m = s % 3600 / 60; // to, co zostało po pełnych godzinach
int sek = s % 60;
cout << g << " " << m << " " << sek << "\n";
int s;
cin >> s;
int sek = s % 60; // najmniejsza jednostka: sekundy
s /= 60; // teraz s to pełne minuty
int m = s % 60;
s /= 60; // teraz s to pełne godziny
int g = s;
cout << g << " " << m << " " << sek << "\n";
Prześledźmy pierwszy sposób dla 3725 sekund:
| wyrażenie | wartość | co znaczy |
|---|---|---|
3725 / 3600 | 1 | jedna pełna godzina |
3725 % 3600 | 125 | sekundy ponad pełne godziny |
125 / 60 | 2 | dwie pełne minuty |
3725 % 60 | 5 | sekundy ponad pełne minuty |
W wyrażeniu s % 3600 / 60 kolejność działań pracuje dla nas: najpierw % (reszta po pełnych godzinach), potem / 60 — od lewej do prawej. A dlaczego sekundy to po prostu s % 60, a nie s % 3600 % 60? Bo pełne godziny też składają się z pełnych minut. Odcięcie ich nie zmienia reszty z dzielenia przez 60.
Zegar z zerami: setw i setfill
Zegar cyfrowy pokazuje 01:02:05, a nie 1:2:5. Z lekcji o wejściu i wyjściu znasz setw(2) i setfill('0') — tutaj pasują idealnie. setfill wystarczy ustawić raz, ale setw działa tylko na najbliższą wypisywaną rzecz, więc stawiasz je przed każdą liczbą.
int s;
cin >> s;
cout << setfill('0');
cout << setw(2) << s / 3600 << ":" << setw(2) << s % 3600 / 60 << ":" << setw(2) << s % 60 << "\n";
45 296 sekund to 12 pełnych godzin (43 200 s), z reszty 2096 s wychodzi 34 pełne minuty (2040 s) i zostaje 56 sekund.
Pieniądze: grosze na złote
Kwoty w programach najlepiej trzymać w groszach, w zmiennej całkowitej — double potrafi przy zaokrągleniach zgubić grosz. Na złote i grosze rozkładasz je tą samą parą: / 100 i % 100.
int gr;
cin >> gr;
cout << gr / 100 << " zl " << gr % 100 << " gr\n";
cout << gr / 100 << "." << setw(2) << setfill('0') << gr % 100 << "\n";
W drugim wierszu kwota wygląda jak na paragonie. Bez setw(2) i setfill('0') zamiast 12.05 zobaczyłbyś 12.5 — a to zupełnie inna kwota: dwanaście złotych i pięćdziesiąt groszy!
W drugą stronę: składanie i różnica czasu
Czasem trzeba odwrotnie: z godzin, minut i sekund zrobić same sekundy. Wtedy mnożysz: g * 3600 + m * 60 + s. Przydaje się to zwłaszcza przy liczeniu, ile czasu minęło między dwiema godzinami: zamieniasz obie na sekundy od północy, odejmujesz, a wynik rozkładasz z powrotem.
int g1, m1, s1, g2, m2, s2;
char z; // tu trafiają dwukropki
cin >> g1 >> z >> m1 >> z >> s1 >> g2 >> z >> m2 >> z >> s2;
int t1 = g1 * 3600 + m1 * 60 + s1;
int t2 = g2 * 3600 + m2 * 60 + s2;
int d = t2 - t1;
cout << d / 3600 << ":" << setfill('0') << setw(2) << d % 3600 / 60 << ":" << setw(2) << d % 60 << "\n";
Start o 8:47:30 to 31 650 sekund od północy, meta o 10:15:10 to 36 910 sekund. Różnica wynosi 5260 sekund: 1 godzina (3600 s), 27 minut (1620 s) i 40 sekund.
Dwukropki wczytujemy do zmiennej typu char — tak jak w lekcji o wejściu i wyjściu.
Wydawanie reszty — dzielenie po kolei
Kasjer wydaje resztę, biorąc za każdym razem największą monetę, która się mieści. To znowu para / i %: ile monet danego nominału — dzielenie; ile zostało jeszcze do wydania — reszta. Potem to samo z kolejną, mniejszą monetą.
int r;
cin >> r; // reszta w złotych
cout << "5 zl: " << r / 5 << "\n";
r %= 5; // tyle zostało do wydania
cout << "2 zl: " << r / 2 << "\n";
r %= 2;
cout << "1 zl: " << r << "\n";
18 zł: trzy monety po 5 zł to 15 zł, zostają 3 zł (18 % 5). Z 3 zł — jedna moneta 2 zł, zostaje 1 zł (3 % 2). Na końcu ta złotówka.
Schemat ile = reszta / nominał; reszta %= nominał; powtarzasz dla każdego nominału, od największego do najmniejszego.
Różne przeliczniki: tygodnie, dni, godziny
Jednostki nie muszą być „po 60” ani „po 100”. Tydzień ma 7 dni, a doba — 24 godziny, więc tydzień to 7 · 24 = 168 godzin. Dzielimy więc najpierw przez 168, a resztę — przez 24:
int h;
cin >> h; // czas w godzinach
int tyg = h / 168; // 7 · 24 = 168 godzin w tygodniu
int dni = h % 168 / 24;
int godz = h % 24;
cout << "tygodnie: " << tyg << ", dni: " << dni << ", godziny: " << godz << "\n";
całość / jej wielkość. 3) Każda następna: całość % wielkość_większej / jej wielkość. 4) Najmniejsza: całość % wielkość_sąsiedniej. Albo od dołu: x % podstawa, potem x /= podstawa — i tak w kółko.
Najpierw odpowiedz w myślach — prześledź program obrót po obrocie — a dopiero potem kliknij „Pokaż odpowiedź”.
int t = 200;
cout << t / 60 << ":" << t % 60;
Pokaż odpowiedź
int s = 4000;
cout << s / 3600 << " " << s % 3600 / 60 << " " << s % 60;
Pokaż odpowiedź
int gr = 307;
cout << gr / 100 << "." << gr % 100;
Pokaż odpowiedź
int d = 100;
cout << d / 7 << " " << d % 7;
Pokaż odpowiedź
int g = 2, m = 5, s = 9;
cout << g * 3600 + m * 60 + s;
Pokaż odpowiedź
int r = 47;
cout << r / 20;
r %= 20;
cout << r / 5;
r %= 5;
cout << r;
Pokaż odpowiedź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
Cyfry liczby: każda pozycja na zawołanie
Z lekcji o pętli while znasz parę n % 10 (ostatnia cyfra) i n / 10 (liczba bez ostatniej cyfry). To tak naprawdę szczególny przypadek rozkładania na jednostki z poprzedniej części: liczba to jedności, dziesiątki, setki, tysiące… — a każda pozycja jest warta 10 razy więcej niż poprzednia. Dzieląc przez 10, 100, 1000 i biorąc reszty z tych dzieleń, możesz wyciąć z liczby dowolny kawałek.
n / 100 = 528
n % 100 = 47
| wyrażenie (n = 52847) | wynik | co to jest |
|---|---|---|
n % 10 | 7 | cyfra jedności |
n / 10 % 10 | 4 | cyfra dziesiątek |
n / 100 % 10 | 8 | cyfra setek |
n / 1000 % 10 | 2 | cyfra tysięcy |
n / 10000 % 10 | 5 | cyfra dziesiątek tysięcy |
n % 100 | 47 | dwie ostatnie cyfry |
n % 1000 | 847 | trzy ostatnie cyfry |
n / 100 | 528 | liczba bez dwóch ostatnich cyfr |
n / 1000 | 52 | liczba bez trzech ostatnich cyfr |
n / 10ᵏ odcina k cyfr z prawej — zostaje lewa część liczby. n % 10ᵏ zostawia k cyfr z prawej — zostaje prawa część. Cyfra stojąca na pozycji k od końca (jedności to pozycja 0) to n / 10ᵏ % 10: najpierw odetnij wszystko na prawo od niej, a potem weź ostatnią cyfrę tego, co zostało.
Cyfry liczby trzycyfrowej
int n;
cin >> n; // liczba trzycyfrowa
int s = n / 100; // setki
int d = n / 10 % 10; // dziesiątki
int j = n % 10; // jedności
cout << s << " " << d << " " << j << "\n";
cout << "suma cyfr: " << s + d + j << "\n";
Kolejność działań jest tu ważna: n / 10 % 10 to (n / 10) % 10. Najpierw odcinamy jedności (507 → 50), potem bierzemy ostatnią cyfrę tego, co zostało (0).
Odwrotny zapis, n % 10 / 10, dawałby zawsze 0: ostatnia cyfra (od 0 do 9) podzielona przez 10.
Dowolna pozycja — pętlą
Gdy numer pozycji k jest wczytywany z wejścia, nie wpiszesz 10ᵏ na sztywno. Możesz za to k razy odciąć ostatnią cyfrę, a potem wziąć ostatnią z tych, które zostały:
long long n;
int k;
cin >> n >> k; // k = 0 to jedności, 1 — dziesiątki…
for (int i = 0; i < k; i++) {
n /= 10; // odcinamy k cyfr z prawej
}
cout << n % 10 << "\n";
Pozycje liczone od zera: w liczbie 9876543210 na pozycji 0 stoi 0, na pozycji 1 — cyfra 1, …, na pozycji 4 — cyfra 4.
Jeśli liczba ma za mało cyfr, po odcięciu zostanie 0, a 0 % 10 to 0. Wynik ma sens: liczbę 52 można zapisać jako 0052 — na pozycji tysięcy stoi „niewidzialne” zero.
Pierwsza cyfra i liczba cyfr
Pierwszej cyfry nie wyciągniesz jednym wzorem, bo nie wiesz z góry, ile liczba ma cyfr. Wystarczy jednak odcinać ostatnią cyfrę, dopóki nie zostanie tylko jedna. Przy okazji możesz policzyć, ile cyfr odcięto:
long long n;
cin >> n;
int ile = 1;
while (n >= 10) {
n /= 10;
ile++;
}
cout << "pierwsza cyfra: " << n << ", cyfr: " << ile << "\n";
Warunek n >= 10 znaczy „liczba ma jeszcze co najmniej dwie cyfry”. Dzięki temu pętla zatrzymuje się, gdy zostaje sama pierwsza cyfra.
Dla liczb jednocyfrowych (także dla 0) pętla nie wykona się ani razu — i dobrze: cała liczba jest wtedy swoją pierwszą cyfrą.
Wszystkie cyfry po kolei — i pułapka z zerem
Przechodzenie po wszystkich cyfrach znasz: weź n % 10, zrób z nią, co trzeba, i odetnij ją przez n /= 10 — dopóki n > 0. Jest jedna pułapka: dla n = 0 taka pętla nie wykona się ani razu, a zero ma przecież jedną cyfrę. Pomaga pętla do … while, która zawsze wykonuje się co najmniej raz:
long long n;
cin >> n;
int ile = 0, suma = 0, parzyste = 0;
do {
int c = n % 10; // ostatnia cyfra
suma += c;
if (c % 2 == 0) {
parzyste++;
}
ile++;
n /= 10; // odcinamy ją
} while (n > 0);
cout << ile << " " << suma << " " << parzyste << "\n";
52847 ma 5 cyfr, ich suma to 5 + 2 + 8 + 4 + 7 = 26, a parzyste są trzy z nich: 2, 8 i 4.
Zauważ, że modulo pracuje tu w dwóch różnych rolach: n % 10 wyciąga cyfrę, a c % 2 sprawdza, czy ta cyfra jest parzysta.
Dla 0 pętla do … while wykonała się raz: jedna cyfra, suma 0, i ta cyfra (zero) jest parzysta.
Budowanie liczby z cyfr
Cyfry można też składać. Doklejenie cyfry c na końcu liczby to w = w * 10 + c — tak odwracałeś liczby w lekcji o while. A doklejenie cyfry na początku? Trzeba wiedzieć, ile jest warta pozycja, na którą ją wstawiasz: 1, 10, 100, … — ta wartość rośnie dziesięć razy z każdą wstawioną cyfrą. Zbudujmy liczbę tylko z parzystych cyfr n, w tej samej kolejności:
long long n;
cin >> n;
long long wynik = 0, p = 1; // p: ile jest warta następna pozycja
while (n > 0) {
int c = n % 10;
if (c % 2 == 0) {
wynik += c * p; // cyfra przed dotychczasowym wynikiem
p *= 10;
}
n /= 10;
}
cout << wynik << "\n";
| cyfra c | parzysta? | wynik | p |
|---|---|---|---|
| 7 | nie | 0 | 1 |
| 4 | tak | 4 | 10 |
| 8 | tak | 84 | 100 |
| 2 | tak | 284 | 1000 |
| 5 | nie | 284 | 1000 |
Cyfry przychodzą od końca (7, 4, 8, 2, 5), a każdą parzystą stawiamy przed tym, co już mamy: 4 → 84 → 284.
Inne systemy liczbowe
Dlaczego właśnie % 10 i / 10? Bo zapisujemy liczby w systemie dziesiątkowym, w którym każda pozycja jest warta 10 razy więcej niż poprzednia. W systemie o podstawie b każda pozycja jest warta b razy więcej, więc cyfry wyciągasz przez % b i / b. Z lekcji o while znasz system dwójkowy (% 2 i / 2). Ten sam program działa dla każdej podstawy od 2 do 10:
long long n;
int b;
cin >> n >> b;
string s = "";
do {
s = char('0' + n % b) + s; // nowa cyfra na początek napisu
n /= b;
} while (n > 0);
cout << s << "\n";
Cyfry wychodzą od końca (najpierw jedności), dlatego każdą doklejamy na początek napisu. char('0' + cyfra) zamienia liczbę od 0 do 9 na znak tej cyfry — pamiętasz kody ASCII z lekcji o typach.
Sprawdzenie dla systemu ósemkowego: 1 · 64 + 4 · 8 + 4 = 100. A dla siódemkowego: 5 · 343 + 6 · 49 + 2 · 7 + 3 = 2026.
Najpierw odpowiedz w myślach — prześledź program obrót po obrocie — a dopiero potem kliknij „Pokaż odpowiedź”.
int n = 4096;
cout << n / 10 % 10;
Pokaż odpowiedź
int n = 4096;
cout << n % 10 / 10;
Pokaż odpowiedź
int n = 123456;
cout << n % 1000 << " " << n / 1000;
Pokaż odpowiedź
int n = 7305;
cout << n / 100 % 10 + n % 10;
Pokaż odpowiedź
int n = 2580, ile = 0;
while (n > 0) {
if (n % 10 == 0) {
ile++;
}
n /= 10;
}
cout << ile;
Pokaż odpowiedź
int n = 11;
string s = "";
while (n > 0) {
s = char('0' + n % 3) + s;
n /= 3;
}
cout << s;
Pokaż odpowiedź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
Zegar, kalendarz i kółeczko
W części 1 zobaczyłeś, że reszty chodzą w kółko: 0, 1, 2, 3, 0, 1, 2, 3… Dokładnie tak zachowuje się wszystko, co się powtarza: godziny na zegarze (po 23 przychodzi 0), dni tygodnia (po niedzieli jest poniedziałek), miesiące w roku, miejsca przy okrągłym stole. Jeśli ponumerujesz takie rzeczy od 0 do n − 1, to przesunięcie o k miejsc do przodu zapiszesz jako (x + k) % n — a modulo samo „zawinie” wynik z powrotem na początek.
Zegar
int h, k;
cin >> h >> k; // jest h:00, minie k godzin
cout << (h + k) % 24 << ":00\n";
20 + 50 = 70 godzin licząc od dzisiejszej północy. Pełne doby (70 / 24 = 2) nas nie interesują — po każdej pełnej dobie zegar pokazuje to samo. Liczy się tylko reszta: 70 % 24 = 22.
240 godzin to dokładnie 10 dób, więc zegar wraca do 5:00. A po 23:00 jedna godzina „przewija” zegar na 0:00.
Dni tygodnia
Ponumerujmy dni tygodnia od zera: poniedziałek to 0, wtorek 1, …, niedziela 6. Jaki dzień będzie za 10 dni, jeśli dziś jest piątek (4)? Siedem dni to pełny tydzień — po nim znowu jest piątek. Zostają jeszcze 3 dni: sobota, niedziela, poniedziałek.
int dzis, k;
cin >> dzis >> k; // 0 = poniedziałek, …, 6 = niedziela
int d = (dzis + k) % 7;
switch (d) {
case 0: cout << "poniedzialek"; break;
case 1: cout << "wtorek"; break;
case 2: cout << "sroda"; break;
case 3: cout << "czwartek"; break;
case 4: cout << "piatek"; break;
case 5: cout << "sobota"; break;
default: cout << "niedziela";
}
cout << "\n";
Instrukcję switch znasz z lekcji o if — zamiana numeru na nazwę to dla niej typowe zadanie. Po niedzieli (6) jeden dzień daje 7 % 7 = 0, czyli poniedziałek. A 700 dni to równo 100 tygodni, więc środa zostaje środą.
Numeracja od 1 — najczęstsza pułapka
Godziny i dni ponumerowaliśmy od 0 — i to nie przypadek. Modulo daje wyniki od 0 do n − 1, więc z numeracją od zera współpracuje idealnie. Co jednak, gdy rzeczy są numerowane od 1: miesiące od 1 do 12, miejsca w rzędzie od 1 do k? Zobacz, co wychodzi, gdy policzymy „na skróty”, jaki miesiąc będzie za k miesięcy:
int m, k;
cin >> m >> k; // miesiąc od 1 do 12 i przesunięcie
cout << (m + k) % 12 << "\n";
int m, k;
cin >> m >> k;
cout << (m - 1 + k) % 12 + 1 << "\n";
Po listopadzie (11) jest grudzień (12), a lewy program wypisał miesiąc 0, którego nie ma. Poprawny przepis ma trzy kroki: odejmij 1 (przejdź na numerację od zera: styczeń to 0, grudzień 11), policz modulo, dodaj 1 (wróć do numeracji od jedynki). Dla listopada i k = 1: 11 − 1 + 1 = 11, potem 11 % 12 = 11, a 11 + 1 = 12 — grudzień. Dla grudnia i k = 1: 12 − 1 + 1 = 12, potem 12 % 12 = 0, a 0 + 1 = 1 — styczeń, tak jak powinno być.
Rzędy i miejsca
Ten sam trik działa przy dzieleniu na grupy. W kinie są rzędy po k miejsc, a bilety numerowane są od 1. Który rząd i które miejsce ma bilet numer x? Przejdź na numerację od zera (x − 1), podziel i weź resztę, a na koniec dodaj 1 do obu wyników:
int k, x;
cin >> k >> x; // k miejsc w rzędzie, bilet numer x
cout << "rzad " << (x - 1) / k + 1 << ", miejsce " << (x - 1) % k + 1 << "\n";
Dla biletu 40 zwykłe 40 / 10 i 40 % 10 dałyby rząd 4 i miejsce 0 — a miejsca 0 nie ma. Z przejściem na zero: 39 / 10 = 3 i 39 % 10 = 9, a po dodaniu jedynek: rząd 4, miejsce 10.
Bilet 37 → 36: rząd 36 / 10 + 1 = 4, miejsce 36 % 10 + 1 = 7.
Chodzenie po kółku
Dzieci stoją w kółku, ponumerowane od 0 do n − 1. Piłkę ma dziecko 0, a przy każdym podaniu piłka przesuwa się o k miejsc. Kto ma piłkę po kolejnych podaniach?
int n, k, t;
cin >> n >> k >> t;
int p = 0;
for (int i = 0; i < t; i++) {
cout << p << " ";
p = (p + k) % n; // k miejsc dalej, z zawijaniem
}
cout << "\n";
Po dziecku 4 piłka „przeskakuje” na początek kółka: (4 + 2) % 5 = 1. Bez modulo numer rósłby bez końca — 0, 2, 4, 6, 8… — a dzieci o takich numerach nie ma.
Zmienna p zawsze jest liczbą od 0 do n − 1, więc nigdy nie wyjdzie poza kółko.
Wzory, które się powtarzają
Wszystko, co powtarza się co n kroków, zapiszesz przez i % n. Litery ABC w kółko, kolorowe paski — a nawet szachownica, na której kolor pola zależy od tego, czy suma numeru wiersza i numeru kolumny jest parzysta:
for (int i = 0; i < 10; i++) {
cout << char('A' + i % 3);
}
cout << "\n";
for (int w = 0; w < 4; w++) {
for (int k = 0; k < 8; k++) {
if ((w + k) % 2 == 0) cout << '#';
else cout << '.';
}
cout << "\n";
}
int n = 8, s = 2; // pola o boku 2 znaków
for (int w = 0; w < n; w++) {
for (int k = 0; k < n; k++) {
if ((w / s + k / s) % 2 == 0) cout << '#';
else cout << '.';
}
cout << "\n";
}
Tu / i % pracują razem: w / s i k / s mówią, w którym „dużym” polu leży znak, a % 2 decyduje o kolorze tego pola.
Cykle w czasie
Sygnalizator świetlny: 30 sekund zielonego, 3 sekundy żółtego, 27 sekund czerwonego — i od nowa. Cały cykl trwa 60 sekund, więc żeby wiedzieć, co świeci w sekundzie t, wystarczy reszta t % 60: numer sekundy w bieżącym cyklu.
long long t;
cin >> t;
int x = t % 60; // która to sekunda bieżącego cyklu
if (x < 30) {
cout << "zielone\n";
} else if (x < 33) {
cout << "zolte\n";
} else {
cout << "czerwone\n";
}
Milion sekund to 16 666 pełnych cykli i jeszcze 40 sekund. 40 nie jest mniejsze od 33, więc świeci czerwone. Ile było pełnych cykli — w ogóle nas nie interesuje. Liczy się tylko reszta.
Dla 123 456 789 012 sekund reszta z dzielenia przez 60 to 12 — zielone. Zmienna t jest typu long long, bo taka liczba nie zmieści się w int; reszta (od 0 do 59) zmieści się już wszędzie.
Najpierw odpowiedz w myślach — prześledź program obrót po obrocie — a dopiero potem kliknij „Pokaż odpowiedź”.
cout << (22 + 5) % 24;
Pokaż odpowiedź
int d = 6;
d = (d + 1) % 7;
cout << d;
Pokaż odpowiedź
int m = 12;
cout << (m - 1 + 2) % 12 + 1;
Pokaż odpowiedź
for (int i = 0; i < 7; i++) {
cout << char('a' + i % 3);
}
Pokaż odpowiedź
int x = 30, k = 8;
cout << (x - 1) / k + 1 << " " << (x - 1) % k + 1;
Pokaż odpowiedź
int p = 0;
for (int i = 0; i < 4; i++) {
p = (p + 3) % 5;
}
cout << p;
Pokaż odpowiedź
9 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
Liczby ujemne i inne pułapki
Do tej pory wszystkie liczby były nieujemne. Gdy pojawia się minus, C++ zachowuje się inaczej, niż podpowiada intuicja ze szkoły — i właśnie tu powstaje najwięcej błędów z modulo. Na końcu części zbierzemy też trzy inne pułapki: liczby z przecinkiem, dzielenie przez zero i przepełnienie.
Jak C++ dzieli liczby ujemne
Dzielenie / w C++ obcina część ułamkową — w stronę zera. −7 / 2 to −3,5, a po obcięciu −3 (nie −4). Reszta jest dobrana tak, żeby równość a = b · q + r nadal była prawdziwa: −7 = 2 · (−3) + r, więc r = −1. Stąd reguła: reszta ma zawsze taki znak jak liczba dzielona (ta po lewej stronie %) — albo jest zerem.
cout << 7 / 2 << " " << 7 % 2 << "\n";
cout << -7 / 2 << " " << -7 % 2 << "\n";
cout << 7 / -2 << " " << 7 % -2 << "\n";
cout << -7 / -2 << " " << -7 % -2 << "\n";
cout << -6 / 3 << " " << -6 % 3 << "\n";
| a, b | q = a / b | r = a % b | b · q + r |
|---|---|---|---|
| 7, 2 | 3 | 1 | 6 + 1 = 7 |
| −7, 2 | −3 | −1 | −6 − 1 = −7 |
| 7, −2 | −3 | 1 | 6 + 1 = 7 |
| −7, −2 | 3 | −1 | −6 − 1 = −7 |
| −6, 3 | −2 | 0 | −6 + 0 = −6 |
W każdym wierszu równość a = b · q + r się zgadza. Znak reszty zależy tylko od a: dla 7 reszta jest dodatnia (nawet przy dzieleniu przez −2), dla −7 — ujemna. W praktyce dzielnik prawie zawsze jest dodatni, więc najważniejsze jest zapamiętanie jednego: ujemna liczba % n daje wynik od −(n − 1) do 0.
Problem: zegar cofany do tyłu
Jest 2:00 w nocy. Która godzina była 5 godzin temu? Na zegarze 21:00. Ale (2 - 5) % 24 to -3 % 24, czyli… −3. Zegar nie pokazuje godziny −3. W matematyce reszta z dzielenia −3 przez 24 wynosi 21 (bo −3 = 24 · (−1) + 21) — ale C++ liczy inaczej.
Najprostsza poprawka: przed wzięciem reszty dodaj pełną dobę. (2 - 5 + 24) % 24 = 21 % 24 = 21. To działa, gdy wiesz, że liczba nie jest „bardzo” ujemna — tu cofamy najwyżej o 23 godziny, więc po dodaniu 24 zawsze wyjdzie liczba nieujemna. Gdy cofasz o dowolnie dużo (np. o 100 godzin), jedno dodanie 24 nie wystarczy. Wtedy pomaga uniwersalny wzór ((a % n) + n) % n:
int h, k;
cin >> h >> k; // jest h:00, cofamy o k godzin
int zle = (h - k) % 24;
int dobrze = ((h - k) % 24 + 24) % 24;
cout << zle << " " << dobrze << "\n";
| krok | a = −90 | a = 12 |
|---|---|---|
a % 24 | −18 | 12 |
+ 24 | 6 | 36 |
% 24 | 6 | 12 |
Pierwsze % sprowadza liczbę do przedziału od −23 do 23. Dodanie 24 robi z niej liczbę od 1 do 47 — na pewno nieujemną. Drugie % jest potrzebne dla liczb, które już były dodatnie: bez niego 12 zamieniłoby się w 36.
a % n, więc niczego nie psuje.
Parzystość liczb ujemnych
Ta sama reguła znaku psuje sprawdzanie nieparzystości: -3 % 2 to −1, więc warunek x % 2 == 1 nie wykryje ujemnych liczb nieparzystych. Bezpieczny zapis to x % 2 != 0. Porównajmy oba na tych samych danych:
int n;
cin >> n;
int zle = 0, dobrze = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (x % 2 == 1) zle++; // pomija ujemne!
if (x % 2 != 0) dobrze++;
}
cout << zle << " " << dobrze << "\n";
Wśród liczb 3, −3, 4, −8 i −1 nieparzyste są trzy. Warunek x % 2 == 1 znalazł tylko jedną — liczbę 3. Dla −3 i −1 reszta wynosi −1.
Sprawdzanie parzystości przez x % 2 == 0 działa dobrze zawsze, bo zero nie ma znaku.
Iloraz zaokrąglony w dół
Skoro C++ obcina w stronę zera, -7 / 2 daje −3, a nie −4. Czasem potrzebujesz jednak ilorazu i reszty „po matematycznemu”: takich, że a = b · q + r i 0 ≤ r < b. Wystarczy jedna poprawka po zwykłym dzieleniu: jeśli reszta wyszła ujemna, dodaj do niej b, a iloraz zmniejsz o 1. Równość nadal się zgadza, bo b · (q − 1) + (r + b) = b · q + r.
long long a, b;
cin >> a >> b; // b > 0
long long q = a / b, r = a % b;
if (r < 0) {
r += b;
q--;
}
cout << q << " " << r << "\n";
Dla −7 i 2: C++ daje q = −3 i r = −1. Reszta jest ujemna, więc poprawiamy: r = −1 + 2 = 1, q = −4. Sprawdzenie: 2 · (−4) + 1 = −7.
Dla −6 i 3 reszta to 0 — nic nie trzeba poprawiać. Dla liczb nieujemnych poprawka też nigdy się nie włącza.
Modulo tylko dla liczb całkowitych
Operator % nie działa na liczbach z przecinkiem. Program, który próbuje policzyć resztę z double, w ogóle się nie skompiluje:
double x = 7.5;
cout << x % 2 << "\n"; // błąd kompilacji
cout << fmod(7.5, 2) << "\n";
Kompilator mówi: „niepoprawne argumenty typów double i int dla operatora %”. Jeśli naprawdę potrzebujesz reszty z liczby z przecinkiem, biblioteka <cmath> ma funkcję fmod: fmod(7.5, 2) to 1.5 (bo 7,5 = 2 · 3 + 1,5).
W zadaniach olimpijskich prawie zawsze da się jednak przejść na liczby całkowite — grosze zamiast złotych, sekundy zamiast godzin z ułamkiem — i tego unikać.
Dzielenie przez zero
a % 0, tak samo jak a / 0, nie ma sensu — i nie daje żadnej dziwnej liczby, tylko wysypuje program (w sprawdzarce zobaczysz błąd wykonania). Jeśli dzielnik pochodzi z wejścia i może być zerem, sprawdź go przed dzieleniem:
int a, b;
cin >> a >> b;
if (b == 0) {
cout << "nie mozna dzielic przez zero\n";
} else {
cout << a % b << "\n";
}
% nie naprawi liczby, która już się przepełniła. W wyrażeniu a * b % m najpierw liczy się a * b — i jeśli ten iloczyn nie mieści się w typie, wynik jest zepsuty, zanim % w ogóle zacznie działać. Jak sobie z tym radzić, zobaczysz w następnej części.
Najpierw odpowiedz w myślach — prześledź program obrót po obrocie — a dopiero potem kliknij „Pokaż odpowiedź”.
cout << -17 % 5;
Pokaż odpowiedź
cout << -17 / 5;
Pokaż odpowiedź
cout << 17 % -5;
Pokaż odpowiedź
int a = -17, n = 5;
cout << (a % n + n) % n;
Pokaż odpowiedź
int x = -9;
if (x % 2 == 1) {
cout << "N";
} else {
cout << "P";
}
Pokaż odpowiedź
int h = 1;
h = (h - 3 + 24) % 24;
cout << h;
Pokaż odpowiedź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
Reszta z ogromnych liczb
Jaka jest ostatnia cyfra liczby 2¹⁰⁰? Ta liczba ma 31 cyfr — nie zmieści się nawet w long long, który mieści liczby do około 9 · 10¹⁸. A przecież pytamy tylko o jedną cyfrę! Okazuje się, że do jej policzenia wcale nie trzeba znać całej liczby. W tej części poznasz najważniejszą sztuczkę z modulo w zadaniach olimpijskich.
Ostatnia cyfra zależy tylko od ostatnich cyfr
Pomnóż pisemnie 47 · 85. Cyfra jedności wyniku powstaje z pomnożenia cyfr jedności: 7 · 5 = 35, więc wynik kończy się na 5 — i rzeczywiście 47 · 85 = 3995. Z dodawaniem jest tak samo: 47 + 85 = 132, a 7 + 5 = 12 — też końcówka 2. Dziesiątki i setki nie mają na cyfrę jedności żadnego wpływu.
int a = 47, b = 85;
cout << (a * b) % 10 << " " << (a % 10) * (b % 10) % 10 << "\n";
cout << (a + b) % 10 << " " << (a % 10 + b % 10) % 10 << "\n";
W każdym wierszu po lewej jest reszta z prawdziwego wyniku, a po prawej — reszta policzona z samych reszt. Zgadzają się. I to nie przypadek: tak samo jest dla każdego dzielnika m, nie tylko dla 10.
Modulo po każdym kroku
To wystarczy, żeby policzyć ostatnią cyfrę 2¹⁰⁰. Mnożymy przez 2 sto razy, ale po każdym mnożeniu zostawiamy tylko ostatnią cyfrę:
int n;
cin >> n;
int w = 1;
for (int i = 0; i < n; i++) {
w = w * 2 % 10; // zostawiamy tylko ostatnią cyfrę
}
cout << w << "\n";
| obrót | prawdziwa potęga | w |
|---|---|---|
| 1 | 2 | 2 |
| 2 | 4 | 4 |
| 3 | 8 | 8 |
| 4 | 16 | 6 |
| 5 | 32 | 2 |
| 6 | 64 | 4 |
| 7 | 128 | 8 |
| 8 | 256 | 6 |
Zmienna w nigdy nie przekracza 9, a mimo to zawsze jest ostatnią cyfrą prawdziwej potęgi. Przy okazji widać, że ostatnie cyfry potęg dwójki powtarzają się co 4: 2, 4, 8, 6, 2, 4, 8, 6… Sto dzieli się przez 4, więc 2¹⁰⁰ kończy się tak jak 2⁴ — na 6.
„Wypisz wynik modulo 10⁹ + 7”
W zadaniach olimpijskich często trzeba policzyć, na ile sposobów można coś zrobić — a takie liczby rosną gigantycznie. Wtedy w treści pojawia się zdanie: „ponieważ wynik może być bardzo duży, wypisz resztę z jego dzielenia przez 1 000 000 007”. Ta liczba nie jest wybrana przypadkowo: to liczba pierwsza, a iloczyn dwóch reszt (każda mniejsza niż 10⁹ + 7) jest mniejszy niż 1,1 · 10¹⁸ — mieści się w long long. Policzmy tak silnię:
const long long MOD = 1000000007;
int n;
cin >> n;
long long w = 1;
for (int i = 1; i <= n; i++) {
w = w * i % MOD;
}
cout << w << "\n";
10! = 3 628 800 jest mniejsze od modulo, więc reszta to po prostu cała silnia. 20! = 2 432 902 008 176 640 000 to już dużo więcej — wypisujemy tylko resztę. A milion silnia ma ponad 5,5 miliona cyfr, a program liczy jej resztę w ułamku sekundy.
long long: w * i sięga 10¹⁵ i więcej, a w int przepełni się, zanim % zdąży zadziałać. 2) Zapis w *= i % MOD to w = w * (i % MOD) — reszta z i, a nie z iloczynu! Pisz w = w * i % MOD.
Odejmowanie modulo — i dlaczego nie dzielenie
Przy odejmowaniu reszt może wyjść liczba ujemna. Reszta z 1 000 000 008 przez 10⁹ + 7 to 1, a z liczby 10 to 10. Ich różnica, 1 − 10 = −9, nie wygląda jak reszta, choć prawdziwa różnica 999 999 998 daje resztę 999 999 998. Na szczęście znasz już poprawkę z części 6:
const long long MOD = 1000000007;
long long a = 1000000008, b = 10;
long long ra = a % MOD, rb = b % MOD;
cout << (ra - rb) % MOD << "\n"; // ujemne!
cout << ((ra - rb) % MOD + MOD) % MOD << "\n"; // poprawione
cout << (a - b) % MOD << "\n"; // dla porównania
Z dzieleniem tak się nie da. Reszta z ilorazu to nie iloraz reszt: (100 / 4) % 7 = 25 % 7 = 4, a (100 % 7) / (4 % 7) = 2 / 4 = 0.
Dzielenie „modulo” istnieje, ale wymaga sprytniejszych narzędzi, które poznasz dużo później. Na razie zapamiętaj: dodawanie, odejmowanie (z poprawką) i mnożenie — tak; dzielenie — nie.
Reszta z liczby zapisanej jako napis
Wróćmy do liczb z tysiącem cyfr. W części 2 sprawdzaliśmy ich podzielność przez 3 sumą cyfr. Teraz umiemy więcej — resztę z dzielenia przez dowolne m. Liczbę 1234 można zbudować cyfra po cyfrze od lewej: 1 → 12 → 123 → 1234 (za każdym razem razy 10 plus nowa cyfra). Skoro reszta z sumy i iloczynu to reszta z reszt, przy każdym kroku możemy zostawiać tylko resztę:
string s;
long long m;
cin >> s >> m;
long long r = 0;
for (char c : s) {
r = (r * 10 + (c - '0')) % m; // dokładamy cyfrę i bierzemy resztę
}
cout << r << "\n";
| cyfra | r · 10 + cyfra | r (reszta z 7) |
|---|---|---|
| 1 | 0 · 10 + 1 = 1 | 1 |
| 2 | 1 · 10 + 2 = 12 | 5 |
| 3 | 5 · 10 + 3 = 53 | 4 |
| 4 | 4 · 10 + 4 = 44 | 2 |
Sprawdzenie: 1234 = 7 · 176 + 2. Zmienna r jest zawsze mniejsza od m, więc r * 10 + 9 nigdy się nie przepełni — niezależnie od tego, ile cyfr ma liczba.
Najpierw odpowiedz w myślach — prześledź program obrót po obrocie — a dopiero potem kliknij „Pokaż odpowiedź”.
cout << (123 * 456) % 10;
Pokaż odpowiedź
cout << (98 + 76) % 10 << " " << (8 + 6) % 10;
Pokaż odpowiedź
long long w = 1;
for (int i = 0; i < 5; i++) {
w = w * 3 % 10;
}
cout << w;
Pokaż odpowiedź
cout << (17 % 5) * (13 % 5) % 5 << " " << 17 * 13 % 5;
Pokaż odpowiedź
string s = "2026";
int r = 0;
for (char c : s) {
r = (r * 10 + c - '0') % 9;
}
cout << r;
Pokaż odpowiedź
cout << (100 / 4) % 7 << " " << (100 % 7) / (4 % 7);
Pokaż odpowiedź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
NWD, dzielenie pisemne i szybkie potęgowanie
Na koniec trzy klasyczne algorytmy, w których modulo gra główną rolę. Każdy z nich spotkasz na olimpiadzie — często jako mały kawałek większego zadania. Wszystkie są krótkie, ale warto je dobrze zrozumieć, a nie tylko zapamiętać.
Algorytm Euklidesa z resztą
Największy wspólny dzielnik (NWD) dwóch liczb to największa liczba, przez którą obie się dzielą: NWD(48, 18) = 6. W lekcji o while liczyłeś go algorytmem Euklidesa, odejmując mniejszą liczbę od większej. Ale odejmowanie tej samej liczby wiele razy z rzędu to nic innego jak dzielenie z resztą! Zamiast odejmować, możemy od razu wziąć resztę: NWD(a, b) = NWD(b, a % b). Gdy druga liczba stanie się zerem, pierwsza jest wynikiem.
long long a, b;
cin >> a >> b;
while (b != 0) {
long long r = a % b;
a = b;
b = r;
}
cout << a << "\n";
| a | b | a % b |
|---|---|---|
| 48 | 18 | 12 |
| 18 | 12 | 6 |
| 12 | 6 | 0 |
| 6 | 0 | — koniec: NWD = 6 |
Dlaczego to takie szybkie? Wersja z odejmowaniem dla liczb 10¹² i 1 odejmowałaby jedynkę bilion razy. Wersja z resztą robi to jednym krokiem: 10¹² % 1 = 0. Reszta „zjada” liczby tak szybko, że dla liczb do 10¹⁸ pętla obróci się najwyżej około 90 razy.
NWW i skracanie ułamków
Z NWD szybko dostaniesz dwie inne rzeczy. Najmniejszą wspólną wielokrotność: NWW(a, b) = a / NWD(a, b) · b — najpierw dzielenie, potem mnożenie, żeby iloczyn a · b nie przepełnił long long. A ułamek skracasz, dzieląc licznik i mianownik przez ich NWD.
long long a, b;
cin >> a >> b;
long long x = a, y = b; // kopie — pętla je zmieni
while (y != 0) {
long long r = x % y;
x = y;
y = r;
}
cout << "NWD = " << x << ", NWW = " << a / x * b << "\n";
cout << a << "/" << b << " = " << a / x << "/" << b / x << "\n";
Ważne: algorytm Euklidesa zmienia swoje zmienne — na końcu x to NWD, a y to 0. Dlatego liczymy go na kopiach, a oryginalne a i b zostają do dalszych obliczeń.
NWW przydaje się, gdy dwie rzeczy powtarzają się w różnych rytmach: autobusy co 4 i co 6 minut spotykają się co NWW(4, 6) = 12 minut. Z części 2 pamiętasz też, że liczby podzielne przez 4 i przez 6 to wielokrotności 12.
Dzielenie pisemne — tyle cyfr, ile chcesz
Typ double daje około 16 dokładnych cyfr. Co, jeśli zadanie każe wypisać 1/7 z tysiącem cyfr po przecinku? Wtedy robimy to, co przy dzieleniu pisemnym na kartce: dzielimy, zapisujemy cyfrę, a resztę mnożymy przez 10 („dopisujemy zero”) i dzielimy dalej.
int a, b, k;
cin >> a >> b >> k;
cout << a / b << ".";
int r = a % b;
for (int i = 0; i < k; i++) {
r *= 10; // dopisujemy zero do reszty
cout << r / b; // kolejna cyfra wyniku
r %= b; // nowa reszta
}
cout << "\n";
| r · 10 | cyfra: r · 10 / 7 | nowa reszta |
|---|---|---|
| 10 | 1 | 3 |
| 30 | 4 | 2 |
| 20 | 2 | 6 |
| 60 | 8 | 4 |
| 40 | 5 | 5 |
| 50 | 7 | 1 |
| 10 | 1 | 3 — to już było! |
Po sześciu krokach reszta wróciła do 1 — a skoro dalsze obliczenia zależą tylko od reszty, wszystko zacznie się powtarzać: 142857 142857 142857… Tak jest z każdym ułamkiem: reszt jest tylko b różnych (od 0 do b − 1), więc prędzej czy później któraś musi się powtórzyć. Dlatego każdy ułamek ma rozwinięcie skończone (gdy reszta stanie się zerem) albo okresowe. W programie dla dużych b reszta po pomnożeniu przez 10 może nie zmieścić się w int — wtedy użyj long long.
Szybkie potęgowanie
Ostatni i najsprytniejszy algorytm tej lekcji. Chcemy policzyć aⁿ mod m dla n = 10¹⁸. Pętla mnożąca n razy wykonałaby 10¹⁸ obrotów. Z lekcji o pętli for wiesz, że komputer robi około 10⁸ prostych obrotów na sekundę, więc trwałoby to ponad 300 lat.
Pomysł: zamiast mnożyć w kółko przez a, podnośmy do kwadratu. a² = a · a, a⁴ = a² · a², a⁸ = a⁴ · a⁴… W 60 mnożeniach dochodzimy do a do potęgi 2⁶⁰ — a to więcej niż 10¹⁸. Każdy wykładnik da się zapisać jako sumę potęg dwójki: to po prostu jego zapis w systemie dwójkowym, który umiesz wyciągać przez % 2 i / 2. Na przykład 13 = 8 + 4 + 1 (dwójkowo 1101), więc a¹³ = a⁸ · a⁴ · a¹.
Algorytm idzie po cyfrach dwójkowych n od końca. W zmiennej pot trzyma kolejne potęgi a, a², a⁴, a⁸, … Gdy bieżąca cyfra dwójkowa n to 1, mnoży wynik przez pot:
long long a, n, m;
cin >> a >> n >> m;
long long wynik = 1 % m, pot = a % m;
while (n > 0) {
if (n % 2 == 1) { // ostatnia cyfra dwójkowa n to 1
wynik = wynik * pot % m;
}
pot = pot * pot % m; // a, a², a⁴, a⁸, …
n /= 2; // odcinamy cyfrę dwójkową
}
cout << wynik << "\n";
| n | n % 2 | pot | wynik |
|---|---|---|---|
| 13 | 1 | 3 (a¹) | 1 · 3 = 3 |
| 6 | 0 | 9 (a²) | 3 — bez zmian |
| 3 | 1 | 81 (a⁴) | 3 · 81 = 243 |
| 1 | 1 | 561 (a⁸ = 6561) | 243 · 561 % 1000 = 323 |
Sprawdzenie: 3¹³ = 1 594 323, a jego trzy ostatnie cyfry to 323. Pętla obraca się tyle razy, ile cyfr ma n w systemie dwójkowym — dla n = 10¹⁸ to 60 obrotów zamiast 10¹⁸.
Wszystkie mnożenia są modulo m, więc liczby nie rosną: przy m około 10⁹ każdy iloczyn dwóch reszt mieści się w long long. Zwróć też uwagę na start wynik = 1 % m zamiast 1 — dla m = 1 każda reszta to 0, nawet z a⁰.
Najpierw odpowiedz w myślach — prześledź program obrót po obrocie — a dopiero potem kliknij „Pokaż odpowiedź”.
long long a = 30, b = 12;
while (b != 0) {
long long r = a % b;
a = b;
b = r;
}
cout << a;
Pokaż odpowiedź
int a = 21, b = 13, ile = 0;
while (b != 0) {
int r = a % b;
a = b;
b = r;
ile++;
}
cout << a << " " << ile;
Pokaż odpowiedź
long long a = 6, b = 10, x = a, y = b;
while (y != 0) {
long long r = x % y;
x = y;
y = r;
}
cout << a / x * b;
Pokaż odpowiedź
int a = 1, b = 8, r = a % b;
for (int i = 0; i < 4; i++) {
r *= 10;
cout << r / b;
r %= b;
}
Pokaż odpowiedź
long long n = 1000000, ile = 0;
while (n > 0) {
n /= 2;
ile++;
}
cout << ile;
Pokaż odpowiedź
long long w = 1, p = 2, n = 10;
while (n > 0) {
if (n % 2 == 1) {
w = w * p % 1000;
}
p = p * p % 1000;
n /= 2;
}
cout << w;
Pokaż odpowiedź
7 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
Baza zadań: modulo w praktyce
Znasz już wszystko, co potrzebne: iloraz i resztę, podzielność, rozkładanie na jednostki, cyfry na dowolnej pozycji, zawijanie w kółko, pułapki z liczbami ujemnymi, działania modulo na ogromnych liczbach i trzy algorytmy olimpijskie. Czas na zadania, które łączą kilka z tych rzeczy naraz. Są ułożone od najłatwiejszego do najtrudniejszego: najpierw rozgrzewka z jednym zastosowaniem %, potem zadania średnie — obroty liczb, systemy liczbowe, kody kreskowe, zera silni, zegar w lustrze — a na końcu trudne, z IBAN-em, wyliczanką, ułamkami okresowymi i wielkim finałem.
Przy każdym zadaniu widać, jakich zagadnień używa — także tych z poprzednich lekcji, jak setw, napisy czy long long. Jeśli coś brzmi obco, wróć do odpowiedniej części — mapa lekcji jest na górze strony. A tu masz wszystkie wzory z lekcji w jednym miejscu:
Ściąga: gotowe wzory z modulo
Iloraz i reszta
q = a / b; r = a % b; // 0 ≤ r < b
Zawsze a = b * q + r. Gdy a < b: iloraz 0, reszta to całe a.
Podzielność
a % b == 0 // a dzieli się przez b x % 2 != 0 // nieparzysta (też ujemna)
Wielokrotności k w przedziale od a do b: b / k - (a - 1) / k.
Rozkładanie na jednostki
g = s / 3600; m = s % 3600 / 60; sek = s % 60;
Grosze: gr / 100 i gr % 100 z setw(2) i setfill('0').
Cyfry liczby
n % 10 // ostatnia cyfra n / 10 // bez ostatniej cyfry n / 100 % 10 // cyfra setek
W systemie o podstawie b: n % b i n / b. Dla zera — do … while.
Zawijanie w kółko
(x + k) % n // od 0 (x - 1 + k) % n + 1 // od 1
W cyklu liczy się tylko reszta: t % długość_cyklu.
Liczby ujemne
((a % n) + n) % n // zawsze 0 … n−1
W C++ reszta ma znak liczby dzielonej: -7 % 3 to −1.
Działania modulo
s = (s + x % m) % m; w = w * x % m; // long long!
Olbrzym w napisie: r = (r * 10 + c - '0') % m. Dzielenia tak nie rozbijesz.
NWD i NWW
while (b != 0) {
r = a % b; a = b; b = r;
} // NWD w a
NWW: a / nwd * b — najpierw dzielenie.
Szybkie potęgowanie
if (n % 2 == 1) w = w * p % m; p = p * p % m; n /= 2;
Start: w = 1 % m, p = a % m. Około 60 obrotów dla n do 10¹⁸.
%. 2) Ustal, czy numeracja jest od 0, czy od 1 — przy numeracji od 1 przejdź na zero, policz i wróć. 3) Sprawdź, czy liczby mogą być ujemne — jeśli tak, użyj ((a % n) + n) % n. 4) Oszacuj wielkość liczb: czy iloczyn zmieści się w long long? Jeśli wynik ma być „modulo m”, bierz resztę po każdym kroku. 5) Gdy liczba nie mieści się w żadnym typie — czytaj ją jako napis. 6) Przetestuj skrajności: 0, 1, wielokrotności dzielnika, największe liczby.
Rozgrzewka · zadania 1–8
Jedno zastosowanie % naraz — reszty, ostatnie cyfry, numeracja od 1, grosze i zegar z kukułką.
Średnie · zadania 9–20
Kilka sztuczek naraz: obroty liczb, systemy liczbowe, olbrzymy zapisane jako napisy, kod kreskowy, zera silni i zegar w lustrze.
Trudne · zadania 21–29
Okresy reszt, IBAN, wyliczanka, ułamki okresowe i strefy czasowe — a na końcu wielki finał: dzień tygodnia dowolnej daty.