C++ · Podstawy · Lekcja 06

Operator modulo w C++

Reszta z dzielenia — znasz ją z podstawówki, a operator % spotkałeś już w kilku lekcjach. Teraz poznasz go naprawdę dobrze: jak liczy się iloraz i reszta, jak sprawdzać podzielność, rozkładać czas i pieniądze na jednostki, wyciągać z liczby dowolną cyfrę, „zawijać” godziny i dni tygodnia, jak nie dać się złapać liczbom ujemnym i jak liczyć resztę z liczb, które nie mieszczą się w żadnym typie. Na koniec trzy algorytmy olimpijskie: NWD, dzielenie pisemne i szybkie potęgowanie. Po każdej części czekają ćwiczenia ze sprawdzarką.

63 ćwiczenia w trakcie lekcji29 zadań w bazie na koniec92 ze sprawdzarką C++

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.

CZĘŚĆ 01–02

Reszta i podzielność

Iloraz i reszta, reszty idące w kółko, kolejność działań, podzielność i wielokrotności.

CZĘŚĆ 03–04

Rozkładanie liczb

Czas i pieniądze na jednostki, dowolna cyfra liczby, inne systemy liczbowe.

CZĘŚĆ 05–06

W kółko i pod kreskę

Zegar, dni tygodnia, numeracja od 1, chodzenie po kółku — i pułapki z liczbami ujemnymi.

CZĘŚĆ 07–08

Modulo na olimpiadzie

Wynik modulo 10⁹ + 7, reszta z olbrzyma, NWD, dzielenie pisemne i szybkie potęgowanie.

Przypomnienie: złota zasada sprawdzarki Sprawdzarka porównuje Twoje wyjście z oczekiwanym znak po znaku, więc wypisujesz dokładnie to, o co prosi zadanie — bez „Podaj liczbę:” i bez dodatkowych słów. Spacje na końcu wiersza są ignorowane, więc 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ęć”.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 3 pełne torebki po 5 cukierków zostają luzem 17 / 5 = 3 17 % 5 = 2 sprawdzenie: 5 · 3 + 2 = 17
Dzielenie / mówi, ile jest pełnych torebek. Modulo % mówi, ile cukierków nie zmieściło się w żadnej pełnej torebce.
dzielenie.cpp
int a = 17, b = 5;
cout << a / b << "\n";   // ile pełnych torebek
cout << a % b << "\n";   // ile cukierków zostaje luzem
▶ Wyjście
3 2

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:

sprawdzenie.cpp
int a, b;
cin >> a >> b;
int q = a / b;   // iloraz
int r = a % b;   // reszta
cout << a << " = " << b << " * " << q << " + " << r << "\n";
▶ Wejście
17 5
▶ Wyjście
17 = 5 * 3 + 2
▶ Inne wejście
40 8
▶ Wyjście
40 = 8 * 5 + 0
▶ Jeszcze inne wejście
3 7
▶ Wyjście
3 = 7 * 0 + 3

Przyjrzyj się kilku dzieleniom naraz. Każdy wiersz tabeli warto sprawdzić w głowie:

aba / ba % bsprawdzenie b · q + r
175325 · 3 + 2 = 17
205405 · 4 + 0 = 20 — dzieli się bez reszty
35035 · 0 + 3 = 3 — piątka nie mieści się ani razu
05005 · 0 + 0 = 0 — nie ma czego dzielić
55105 · 1 + 0 = 5 — jedna pełna torebka
99109910 · 9 + 9 = 99
10071427 · 14 + 2 = 100
1000333313 · 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żeniemożliwe wyniki
x % 20 albo 1 — parzysta albo nieparzysta
x % 10od 0 do 9 — ostatnia cyfra liczby
x % 7od 0 do 6 — jak siedem dni tygodnia
x % 24od 0 do 23 — jak godziny na zegarze
x % 60od 0 do 59 — jak minuty i sekundy
x % 1zawsze 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):

reszty_po_kolei.cpp
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";
}
▶ Wyjście
a a/4 a%4 0 0 0 1 0 1 2 0 2 3 0 3 4 1 0 5 1 1 6 1 2 7 1 3 8 2 0 9 2 1

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:

kolejnosc.cpp
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
▶ Wyjście
3 0 4 8 98
% liczy się jak mnożenie Operator % 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ą”.

procent_rowna_sie.cpp
int x = 1234;
x %= 100;          // x = x % 100
cout << x << "\n";
x %= 7;            // 34 % 7
cout << x << "\n";
▶ Wyjście
34 6

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.

Sprawdź się w głowie

Najpierw odpowiedz w myślach — prześledź program obrót po obrocie — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
cout << 23 % 4;
Pokaż odpowiedź
3Czwórka mieści się w 23 pięć razy (4 · 5 = 20), zostają 3.
Co wypisze ten fragment?
cout << 4 % 23;
Pokaż odpowiedź
423 nie mieści się w czwórce ani razu — iloraz to 0, a cała czwórka zostaje jako reszta.
Iloraz i reszta. Co wypisze program?
cout << 50 / 7 << " " << 50 % 7;
Pokaż odpowiedź
7 17 · 7 = 49, zostaje 1. Sprawdzenie: 7 · 7 + 1 = 50.
Kolejność działań. Co wypisze program?
cout << 10 - 10 % 4 * 2;
Pokaż odpowiedź
6Najpierw 10 % 4 = 2, potem 2 * 2 = 4 (od lewej do prawej), a na końcu odejmowanie: 10 − 4 = 6.
Operator %=. Co wypisze program?
int x = 47;
x %= 10;
x %= 4;
cout << x;
Pokaż odpowiedź
347 % 10 = 7 (ostatnia cyfra), potem 7 % 4 = 3.
Reszty w pętli. Co wypisze ten fragment?
for (int i = 1; i <= 8; i++) {
    cout << i % 3;
}
Pokaż odpowiedź
12012012Reszty z dzielenia przez 3 idą w kółko: 1, 2, 0, 1, 2, 0, 1, 2.
Co wypisze ten fragment?
cout << 1000000 % 1000 << " " << 999999 % 1000;
Pokaż odpowiedź
0 999Reszta z dzielenia przez 1000 to trzy ostatnie cyfry liczby: 000 (czyli 0) i 999.

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.

czy_dzieli.cpp
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";
}
▶ Wejście
36 4
▶ Wyjście
36 dzieli sie przez 4
▶ Inne wejście
36 5
▶ Wyjście
36 nie dzieli sie przez 5, reszta 1

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.

parzyste.cpp
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";
▶ Wejście
6 4 7 -2 -9 0 15
▶ Wyjście
3 3

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.

zdaniewarunek w C++
a dzieli się przez ba % b == 0
a jest wielokrotnością ba % b == 0
b jest dzielnikiem aa % b == 0
a jest dzielnikiem b (a dzieli b)b % a == 0
a jest parzystaa % 2 == 0
a jest nieparzystaa % 2 != 0
a kończy się zerema % 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:

wielokrotnosci.cpp
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";
▶ Wejście
20 6
▶ Wyjście
6 12 18 razem: 3

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:

wielokrotnosci_wzor.cpp
long long a, b, k;
cin >> a >> b >> k;
cout << b / k - (a - 1) / k << "\n";
▶ Wejście
10 40 7
▶ Wyjście
4
▶ Inne wejście
1 1000000000000000000 3
▶ Wyjście
333333333333333333

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:

po_piec.cpp
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
    }
}
▶ Wyjście
1 2 3 4 5 6 7 8 9 10 11 12 13 14

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:

cztery_i_szesc.cpp
for (int i = 1; i <= 50; i++) {
    if (i % 4 == 0 && i % 6 == 0) {
        cout << i << " ";
    }
}
cout << "\n";
▶ Wyjście
12 24 36 48

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ł.

przestepne.cpp
for (int r = 1896; r <= 1912; r++) {
    if ((r % 4 == 0 && r % 100 != 0) || r % 400 == 0) {
        cout << r << " ";
    }
}
cout << "\n";
▶ Wyjście
1896 1904 1908 1912

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:

cecha_trzy.cpp
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";
}
▶ Wejście
123456789123456789123456789
▶ Wyjście
suma cyfr: 135 dzieli sie przez 3

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.

Sprawdź się w głowie

Najpierw odpowiedz w myślach — prześledź program obrót po obrocie — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
cout << (91 % 7 == 0);
Pokaż odpowiedź
191 = 7 · 13, więc reszta to 0 i porównanie jest prawdziwe — cout wypisuje prawdę jako 1.
Ile liczb policzy pętla?
int ile = 0;
for (int i = 1; i <= 30; i++) {
    if (i % 4 == 0) {
        ile++;
    }
}
cout << ile;
Pokaż odpowiedź
74, 8, 12, 16, 20, 24, 28 — siedem liczb. Wzór daje to samo: 30 / 4 = 7.
Co wypisze ten fragment?
if (12 % 8 == 0 && 12 % 3 == 0) {
    cout << "A";
} else {
    cout << "B";
}
Pokaż odpowiedź
B12 dzieli się przez 3, ale nie przez 8 (12 % 8 to 4). Przy && oba warunki muszą być prawdziwe.
Czy rok 2100 będzie przestępny? Co wypisze program?
int r = 2100;
cout << ((r % 4 == 0 && r % 100 != 0) || r % 400 == 0);
Pokaż odpowiedź
02100 dzieli się przez 4 i przez 100, ale nie przez 400 — nie będzie przestępny.
Wielokrotności siódemki od 50 do 100. Co wypisze program?
cout << 100 / 7 - 49 / 7;
Pokaż odpowiedź
7Do 100 jest 14 wielokrotności siódemki, do 49 — 7. Różnica: 7 liczb (56, 63, 70, 77, 84, 91, 98).
Co k-ty raz. Co wypisze ten fragment?
for (int i = 1; i <= 7; i++) {
    cout << i;
    if (i % 3 == 0) {
        cout << "|";
    }
}
Pokaż odpowiedź
123|456|7Kreska pojawia się po każdej liczbie podzielnej przez 3: po 3 i po 6.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

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ę.

Wszystkie ćwiczenia z tej części w sprawdzarce →

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

minuty.cpp
int t;
cin >> t;                 // czas w minutach
cout << t / 60 << " h " << t % 60 << " min\n";
▶ Wejście
135
▶ Wyjście
2 h 15 min
▶ Inne wejście
59
▶ Wyjście
0 h 59 min

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.

z_gory.cpp
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";
▶ Wejście
3725
▶ Wyjście
1 2 5
po_kolei.cpp
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";
▶ Wejście
3725
▶ Wyjście
1 2 5

Prześledźmy pierwszy sposób dla 3725 sekund:

wyrażeniewartośćco znaczy
3725 / 36001jedna pełna godzina
3725 % 3600125sekundy ponad pełne godziny
125 / 602dwie pełne minuty
3725 % 605sekundy 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ą.

zegar_hms.cpp
int s;
cin >> s;
cout << setfill('0');
cout << setw(2) << s / 3600 << ":" << setw(2) << s % 3600 / 60 << ":" << setw(2) << s % 60 << "\n";
▶ Wejście
3725
▶ Wyjście
01:02:05
▶ Inne wejście
45296
▶ Wyjście
12:34:56

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.

grosze.cpp
int gr;
cin >> gr;
cout << gr / 100 << " zl " << gr % 100 << " gr\n";
cout << gr / 100 << "." << setw(2) << setfill('0') << gr % 100 << "\n";
▶ Wejście
1205
▶ Wyjście
12 zl 5 gr 12.05

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.

roznica_czasu.cpp
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";
▶ Wejście
08:47:30 10:15:10
▶ Wyjście
1:27:40

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ą.

reszta_monety.cpp
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";
▶ Wejście
18
▶ Wyjście
5 zl: 3 2 zl: 1 1 zl: 1

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:

tygodnie.cpp
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";
▶ Wejście
200
▶ Wyjście
tygodnie: 1, dni: 1, godziny: 8
Przepis na rozkładanie 1) Ustal, ile najmniejszych jednostek ma każda większa (minuta = 60 s, godzina = 3600 s, tydzień = 168 h). 2) Największa jednostka: 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.
Sprawdź się w głowie

Najpierw odpowiedz w myślach — prześledź program obrót po obrocie — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
int t = 200;
cout << t / 60 << ":" << t % 60;
Pokaż odpowiedź
3:20200 minut to 3 pełne godziny (180 minut) i 20 minut.
Co wypisze ten fragment?
int s = 4000;
cout << s / 3600 << " " << s % 3600 / 60 << " " << s % 60;
Pokaż odpowiedź
1 6 40Jedna pełna godzina, z reszty 400 s wychodzi 6 pełnych minut (360 s) i zostaje 40 s.
Gdzie jest błąd? Co wypisze ten fragment?
int gr = 307;
cout << gr / 100 << "." << gr % 100;
Pokaż odpowiedź
3.7Bez setw(2) i setfill('0') zero z przodu groszy znika — 3 zł 7 gr wygląda jak 3,70 zł.
Co wypisze ten fragment?
int d = 100;
cout << d / 7 << " " << d % 7;
Pokaż odpowiedź
14 2100 dni to 14 pełnych tygodni (98 dni) i 2 dni.
Składanie z powrotem. Co wypisze program?
int g = 2, m = 5, s = 9;
cout << g * 3600 + m * 60 + s;
Pokaż odpowiedź
75097200 + 300 + 9 = 7509 sekund.
Banknoty 20 zł, monety 5 zł i 1 zł. Co wypisze program?
int r = 47;
cout << r / 20;
r %= 20;
cout << r / 5;
r %= 5;
cout << r;
Pokaż odpowiedź
212Dwa banknoty po 20 zł (zostaje 7), jedna moneta 5 zł (zostają 2) i dwie złotówki.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

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ę.

Wszystkie ćwiczenia z tej części w sprawdzarce →

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 = 52847. Dzielenie przez 100 odcina dwie ostatnie cyfry, a reszta z dzielenia przez 100 to właśnie te dwie cyfry.
wyrażenie (n = 52847)wynikco to jest
n % 107cyfra jedności
n / 10 % 104cyfra dziesiątek
n / 100 % 108cyfra setek
n / 1000 % 102cyfra tysięcy
n / 10000 % 105cyfra dziesiątek tysięcy
n % 10047dwie ostatnie cyfry
n % 1000847trzy ostatnie cyfry
n / 100528liczba bez dwóch ostatnich cyfr
n / 100052liczba bez trzech ostatnich cyfr
Dwie pary nożyczek: / 10ᵏ i % 10ᵏ 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

trzycyfrowa.cpp
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";
▶ Wejście
507
▶ Wyjście
5 0 7 suma cyfr: 12

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:

pozycja_k.cpp
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";
▶ Wejście
9876543210 4
▶ Wyjście
4
▶ Inne wejście
52 3
▶ Wyjście
0

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:

pierwsza_cyfra.cpp
long long n;
cin >> n;
int ile = 1;
while (n >= 10) {
    n /= 10;
    ile++;
}
cout << "pierwsza cyfra: " << n << ", cyfr: " << ile << "\n";
▶ Wejście
52847
▶ Wyjście
pierwsza cyfra: 5, cyfr: 5
▶ Inne wejście
7
▶ Wyjście
pierwsza cyfra: 7, cyfr: 1

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:

cyfry_do_while.cpp
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";
▶ Wejście
52847
▶ Wyjście
5 26 3
▶ Inne wejście
0
▶ Wyjście
1 0 1

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:

parzyste_cyfry.cpp
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";
▶ Wejście
52847
▶ Wyjście
284
cyfra cparzysta?wynikp
7nie01
4tak410
8tak84100
2tak2841000
5nie2841000

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:

system_b.cpp
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";
▶ Wejście
100 8
▶ Wyjście
144
▶ Inne wejście
13 2
▶ Wyjście
1101
▶ Jeszcze inne wejście
2026 7
▶ Wyjście
5623

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.

Sprawdź się w głowie

Najpierw odpowiedz w myślach — prześledź program obrót po obrocie — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
int n = 4096;
cout << n / 10 % 10;
Pokaż odpowiedź
94096 / 10 = 409, a 409 % 10 = 9 — cyfra dziesiątek.
Odwrotna kolejność. Co wypisze ten fragment?
int n = 4096;
cout << n % 10 / 10;
Pokaż odpowiedź
0Najpierw 4096 % 10 = 6, potem 6 / 10 = 0. Ostatnia cyfra podzielona przez 10 to zawsze 0.
Co wypisze ten fragment?
int n = 123456;
cout << n % 1000 << " " << n / 1000;
Pokaż odpowiedź
456 123% 1000 zostawia trzy ostatnie cyfry, / 1000 je odcina.
Co wypisze ten fragment?
int n = 7305;
cout << n / 100 % 10 + n % 10;
Pokaż odpowiedź
8Cyfra setek to 3, cyfra jedności to 5, a 3 + 5 = 8.
Co policzy ta pętla?
int n = 2580, ile = 0;
while (n > 0) {
    if (n % 10 == 0) {
        ile++;
    }
    n /= 10;
}
cout << ile;
Pokaż odpowiedź
1Pętla liczy zera w zapisie liczby. Cyfry od końca: 0, 8, 5, 2 — jedno zero.
System trójkowy. Co wypisze program?
int n = 11;
string s = "";
while (n > 0) {
    s = char('0' + n % 3) + s;
    n /= 3;
}
cout << s;
Pokaż odpowiedź
10211 % 3 = 2, potem 3 % 3 = 0, potem 1 % 3 = 1. Odczytane od końca: 102. Sprawdzenie: 1 · 9 + 0 · 3 + 2 = 11.

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

zegar.cpp
int h, k;
cin >> h >> k;     // jest h:00, minie k godzin
cout << (h + k) % 24 << ":00\n";
▶ Wejście
20 50
▶ Wyjście
22:00
▶ Inne wejście
23 1
▶ Wyjście
0:00
▶ Jeszcze inne wejście
5 240
▶ Wyjście
5:00

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.

+3 dni Pn0 Wt1 Śr2 Cz3 Pt4 So5 Nd6 piątek + 10 dni 10 = 7 (pełne kółko) + 3 (4 + 10) % 7 = 0
Pełne okrążenie (7 dni) niczego nie zmienia — liczy się tylko reszta z dzielenia przez 7. Piątek + 10 dni = piątek + 3 dni = poniedziałek.
dzien_tygodnia.cpp
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";
▶ Wejście
4 10
▶ Wyjście
poniedzialek
▶ Inne wejście
6 1
▶ Wyjście
poniedzialek
▶ Jeszcze inne wejście
2 700
▶ Wyjście
sroda

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:

miesiac_zle.cpp
int m, k;
cin >> m >> k;      // miesiąc od 1 do 12 i przesunięcie
cout << (m + k) % 12 << "\n";
▶ Wejście
11 1
▶ Wyjście
0
miesiac_dobrze.cpp
int m, k;
cin >> m >> k;
cout << (m - 1 + k) % 12 + 1 << "\n";
▶ Wejście
11 1
▶ Wyjście
12

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ć.

Przesunięcie o k w kółku z n pozycjami numeracja od 0: (x + k) % n numeracja od 1: (x - 1 + k) % n + 1 Zapamiętaj oba wzory — drugi zobaczysz w bardzo wielu zadaniach z miesiącami, miejscami, numerami dzieci w kółku i stronami książki.

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:

kino.cpp
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";
▶ Wejście
10 37
▶ Wyjście
rzad 4, miejsce 7
▶ Inne wejście
10 40
▶ Wyjście
rzad 4, miejsce 10

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?

pilka.cpp
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";
▶ Wejście
5 2 7
▶ Wyjście
0 2 4 1 3 0 2

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:

abc.cpp
for (int i = 0; i < 10; i++) {
    cout << char('A' + i % 3);
}
cout << "\n";
▶ Wyjście
ABCABCABCA
szachownica.cpp
for (int w = 0; w < 4; w++) {
    for (int k = 0; k < 8; k++) {
        if ((w + k) % 2 == 0) cout << '#';
        else cout << '.';
    }
    cout << "\n";
}
▶ Wyjście
#.#.#.#. .#.#.#.# #.#.#.#. .#.#.#.#
duza_szachownica.cpp
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";
}
▶ Wyjście
##..##.. ##..##.. ..##..## ..##..## ##..##.. ##..##.. ..##..## ..##..##

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.

swiatla.cpp
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";
}
▶ Wejście
1000000
▶ Wyjście
czerwone
▶ Inne wejście
123456789012
▶ Wyjście
zielone

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.

Sprawdź się w głowie

Najpierw odpowiedz w myślach — prześledź program obrót po obrocie — a dopiero potem kliknij „Pokaż odpowiedź”.

Jest 22:00. Która godzina będzie za 5 godzin?
cout << (22 + 5) % 24;
Pokaż odpowiedź
327 % 24 = 3 — trzecia w nocy.
Dzień po niedzieli. Co wypisze program?
int d = 6;
d = (d + 1) % 7;
cout << d;
Pokaż odpowiedź
07 % 7 = 0 — po niedzieli (6) jest poniedziałek (0).
Grudzień + 2 miesiące. Co wypisze program?
int m = 12;
cout << (m - 1 + 2) % 12 + 1;
Pokaż odpowiedź
2(11 + 2) % 12 = 1, plus 1 daje 2 — luty.
Co wypisze ten fragment?
for (int i = 0; i < 7; i++) {
    cout << char('a' + i % 3);
}
Pokaż odpowiedź
abcabcai % 3 przyjmuje kolejno 0, 1, 2, 0, 1, 2, 0 — litery a, b, c w kółko.
Bilet 30, rzędy po 8 miejsc. Co wypisze program?
int x = 30, k = 8;
cout << (x - 1) / k + 1 << " " << (x - 1) % k + 1;
Pokaż odpowiedź
4 629 / 8 = 3 i 29 % 8 = 5, po dodaniu jedynek: rząd 4, miejsce 6.
Piłka w kółku 5 dzieci, podania o 3. Co wypisze program?
int p = 0;
for (int i = 0; i < 4; i++) {
    p = (p + 3) % 5;
}
cout << p;
Pokaż odpowiedź
2Kolejno 3, 1 (6 % 5), 4, 2 (7 % 5).
Ćwiczenia · teraz Ty

9 ćwiczeń do tej części

0 / 9 zaliczonych

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ę.

Wszystkie ćwiczenia z tej części w sprawdzarce →

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.

ujemne.cpp
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";
▶ Wyjście
3 1 -3 -1 -3 1 3 -1 -2 0
a, bq = a / br = a % bb · q + r
7, 2316 + 1 = 7
−7, 2−3−1−6 − 1 = −7
7, −2−316 + 1 = 7
−7, −23−1−6 − 1 = −7
−6, 3−20−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:

cofanie.cpp
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";
▶ Wejście
2 5
▶ Wyjście
-3 21
▶ Inne wejście
10 100
▶ Wyjście
-18 6
▶ Jeszcze inne wejście
15 3
▶ Wyjście
12 12
kroka = −90a = 12
a % 24−1812
+ 24636
% 24612

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.

Reszta zawsze od 0 do n − 1 ((a % n) + n) % n Używaj tego wzoru za każdym razem, gdy liczba, z której bierzesz resztę, może być ujemna: przy cofaniu czasu, ruchu w lewo po kółku, odejmowaniu. Dla liczb nieujemnych daje dokładnie to samo co zwykłe 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:

nieparzyste.cpp
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";
▶ Wejście
5 3 -3 4 -8 -1
▶ Wyjście
1 3

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.

dzielenie_w_dol.cpp
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";
▶ Wejście
-7 2
▶ Wyjście
-4 1
▶ Inne wejście
-6 3
▶ Wyjście
-2 0

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_blad.cpp
double x = 7.5;
cout << x % 2 << "\n";    // błąd kompilacji
▶ Kompilator
error: invalid operands of types 'double' and 'int' to binary 'operator%'
fmod.cpp
cout << fmod(7.5, 2) << "\n";
▶ Wyjście
1.5

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:

bezpieczne.cpp
int a, b;
cin >> a >> b;
if (b == 0) {
    cout << "nie mozna dzielic przez zero\n";
} else {
    cout << a % b << "\n";
}
▶ Wejście
10 0
▶ Wyjście
nie mozna dzielic przez zero
▶ Inne wejście
10 3
▶ Wyjście
1
Przepełnienie dzieje się przed modulo Ostatnia pułapka: % 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.
Sprawdź się w głowie

Najpierw odpowiedz w myślach — prześledź program obrót po obrocie — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
cout << -17 % 5;
Pokaż odpowiedź
-2Reszta ma znak liczby dzielonej: −17 = 5 · (−3) + (−2).
Co wypisze ten fragment?
cout << -17 / 5;
Pokaż odpowiedź
-3−17 / 5 = −3,4, a C++ obcina w stronę zera: −3.
Co wypisze ten fragment?
cout << 17 % -5;
Pokaż odpowiedź
2Liczba dzielona (17) jest dodatnia, więc reszta też: 17 = (−5) · (−3) + 2.
Wzór na resztę od 0 do n − 1. Co wypisze program?
int a = -17, n = 5;
cout << (a % n + n) % n;
Pokaż odpowiedź
3−17 % 5 = −2, potem −2 + 5 = 3, a 3 % 5 = 3. Sprawdzenie: −17 = 5 · (−4) + 3.
Pułapka z nieparzystością. Co wypisze program?
int x = -9;
if (x % 2 == 1) {
    cout << "N";
} else {
    cout << "P";
}
Pokaż odpowiedź
P−9 % 2 to −1, a nie 1 — warunek jest fałszywy i program twierdzi, że −9 jest parzyste. Dlatego pisz x % 2 != 0.
Jest 1:00. Która godzina była 3 godziny temu?
int h = 1;
h = (h - 3 + 24) % 24;
cout << h;
Pokaż odpowiedź
221 − 3 = −2, po dodaniu 24: 22. Bez dodania doby wyszłoby −2.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

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ę.

Wszystkie ćwiczenia z tej części w sprawdzarce →

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.

ostatnie_cyfry.cpp
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";
▶ Wyjście
5 5 2 2

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.

Reszta z sumy i reszta z iloczynu (a + b) % m = (a % m + b % m) % m (a * b) % m = (a % m) * (b % m) % m Resztę możesz więc brać z każdego składnika i czynnika z osobna — i po każdym kroku obliczeń. Wynik się nie zmieni, a liczby zostaną małe. (Dotyczy to liczb nieujemnych; przy odejmowaniu trzeba uważać — o tym za chwilę.)

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ę:

ostatnia_cyfra_potegi.cpp
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";
▶ Wejście
100
▶ Wyjście
6
▶ Inne wejście
10
▶ Wyjście
4
obrótprawdziwa potęgaw
122
244
388
4166
5322
6644
71288
82566

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ę:

silnia_mod.cpp
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";
▶ Wejście
10
▶ Wyjście
3628800
▶ Inne wejście
20
▶ Wyjście
146326063
▶ Jeszcze inne wejście
1000000
▶ Wyjście
641102369

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.

Dwie pułapki 1) Wynik musi być w 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:

roznica_mod.cpp
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
▶ Wyjście
-9 999999998 999999998

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ę:

reszta_olbrzyma.cpp
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";
▶ Wejście
1234 7
▶ Wyjście
2
▶ Inne wejście
123456789123456789123456789 1000000007
▶ Wyjście
308641892
cyfrar · 10 + cyfrar (reszta z 7)
10 · 10 + 1 = 11
21 · 10 + 2 = 125
35 · 10 + 3 = 534
44 · 10 + 4 = 442

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.

Sprawdź się w głowie

Najpierw odpowiedz w myślach — prześledź program obrót po obrocie — a dopiero potem kliknij „Pokaż odpowiedź”.

Bez kalkulatora: co wypisze ten fragment?
cout << (123 * 456) % 10;
Pokaż odpowiedź
8Liczy się tylko 3 · 6 = 18, czyli końcówka 8. (I rzeczywiście 123 · 456 = 56 088.)
Co wypisze ten fragment?
cout << (98 + 76) % 10 << " " << (8 + 6) % 10;
Pokaż odpowiedź
4 498 + 76 = 174, a 8 + 6 = 14 — obie liczby kończą się czwórką.
Ostatnia cyfra 3⁵. Co wypisze program?
long long w = 1;
for (int i = 0; i < 5; i++) {
    w = w * 3 % 10;
}
cout << w;
Pokaż odpowiedź
3Kolejno 3, 9, 7 (27), 1 (21), 3. Rzeczywiście 3⁵ = 243.
Co wypisze ten fragment?
cout << (17 % 5) * (13 % 5) % 5 << " " << 17 * 13 % 5;
Pokaż odpowiedź
1 12 · 3 = 6, a 6 % 5 = 1. Z drugiej strony 17 · 13 = 221, a 221 % 5 = 1.
Reszta z napisu. Co wypisze program?
string s = "2026";
int r = 0;
for (char c : s) {
    r = (r * 10 + c - '0') % 9;
}
cout << r;
Pokaż odpowiedź
1Kolejno 2, 2 (20 % 9), 4 (22 % 9), 1 (46 % 9). Sprawdzenie: 2026 = 9 · 225 + 1.
Czy dzielenie też można „rozbić na reszty”?
cout << (100 / 4) % 7 << " " << (100 % 7) / (4 % 7);
Pokaż odpowiedź
4 0Nie: 25 % 7 = 4, a 2 / 4 = 0. Reszta z ilorazu to nie iloraz reszt.
Ćwiczenia · teraz Ty

8 ćwiczeń do tej części

0 / 8 zaliczonych

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ę.

Wszystkie ćwiczenia z tej części w sprawdzarce →

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.

nwd.cpp
long long a, b;
cin >> a >> b;
while (b != 0) {
    long long r = a % b;
    a = b;
    b = r;
}
cout << a << "\n";
▶ Wejście
48 18
▶ Wyjście
6
▶ Inne wejście
1071 462
▶ Wyjście
21
▶ Jeszcze inne wejście
1000000000000 1
▶ Wyjście
1
aba % b
481812
18126
1260
60— 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.

nww_ulamek.cpp
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";
▶ Wejście
4 6
▶ Wyjście
NWD = 2, NWW = 12 4/6 = 2/3
▶ Inne wejście
1000000000 999999999
▶ Wyjście
NWD = 1, NWW = 999999999000000000 1000000000/999999999 = 1000000000/999999999

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.

pisemne.cpp
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";
▶ Wejście
1 7 20
▶ Wyjście
0.14285714285714285714
▶ Inne wejście
22 7 10
▶ Wyjście
3.1428571428
r · 10cyfra: r · 10 / 7nowa reszta
1013
3042
2026
6084
4055
5071
1013 — 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:

szybka_potega.cpp
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";
▶ Wejście
3 13 1000
▶ Wyjście
323
▶ Inne wejście
2 1000000000000000000 1000000007
▶ Wyjście
719476260
nn % 2potwynik
1313 (a¹)1 · 3 = 3
609 (a²)3 — bez zmian
3181 (a⁴)3 · 81 = 243
11561 (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⁰.

Sprawdź się w głowie

Najpierw odpowiedz w myślach — prześledź program obrót po obrocie — a dopiero potem kliknij „Pokaż odpowiedź”.

NWD(30, 12). Co wypisze program?
long long a = 30, b = 12;
while (b != 0) {
    long long r = a % b;
    a = b;
    b = r;
}
cout << a;
Pokaż odpowiedź
6(30, 12) → (12, 6) → (6, 0). NWD = 6.
Ile obrotów zrobi algorytm Euklidesa?
int a = 21, b = 13, ile = 0;
while (b != 0) {
    int r = a % b;
    a = b;
    b = r;
    ile++;
}
cout << a << " " << ile;
Pokaż odpowiedź
1 6(21, 13) → (13, 8) → (8, 5) → (5, 3) → (3, 2) → (2, 1) → (1, 0). To kolejne liczby Fibonacciego — dla nich Euklides robi najwięcej kroków.
NWW przez NWD. Co wypisze program?
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ź
30NWD(6, 10) = 2, więc NWW = 6 / 2 · 10 = 30.
Dzielenie pisemne 1/8. Co wypisze ta pętla?
int a = 1, b = 8, r = a % b;
for (int i = 0; i < 4; i++) {
    r *= 10;
    cout << r / b;
    r %= b;
}
Pokaż odpowiedź
12501/8 = 0,125 — po trzech cyfrach reszta to 0, więc dalej są już same zera.
Ile razy można podzielić milion przez 2, zanim zostanie 0?
long long n = 1000000, ile = 0;
while (n > 0) {
    n /= 2;
    ile++;
}
cout << ile;
Pokaż odpowiedź
20Milion ma 20 cyfr w systemie dwójkowym (2¹⁹ ≤ 1 000 000 < 2²⁰). Tyle obrotów zrobiłoby szybkie potęgowanie dla n = 10⁶.
Szybkie potęgowanie: 2¹⁰ mod 1000. Co wypisze program?
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ź
2410 = 8 + 2, więc 2¹⁰ = 2⁸ · 2² = 256 · 4 = 1024, a 1024 % 1000 = 24.

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¹⁸.

Jak rozwiązywać zadania z modulo 1) Zapytaj: co tu się powtarza w kółko? Doba, tydzień, cykl świateł, cyfry — to sygnał do %. 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.
średnie

Średnie · zadania 9–20

Kilka sztuczek naraz: obroty liczb, systemy liczbowe, olbrzymy zapisane jako napisy, kod kreskowy, zera silni i zegar w lustrze.

9 Batony w paczkachśrednie✓ zaliczone Batony pojedynczo albo w paczkach po k. Jak najtaniej kupić co najmniej n? n / k i n % ktrzy możliwościminlong long Rozwiąż 10 Obracanie liczbyśrednie✓ zaliczone Ostatnia cyfra wędruje na początek — k razy, a k może mieć 18 cyfr. n % 10 * p + n / 10k % liczba cyfrcykl Rozwiąż 11 Z systemu b na system cśrednie✓ zaliczone Przelicz zapis liczby z systemu o podstawie b na system o podstawie c. x = x * b + cyfra% c i / cstring Rozwiąż 12 Przez 7, 11 i 13średnie✓ zaliczone Liczba ma do 10 000 cyfr. Przez które z liczb 7, 11, 13 się dzieli? r = (r * 10 + cyfra) % mtrzy reszty narazstring Rozwiąż 13 Kod kreskowy EAN-13średnie✓ zaliczone Dopisz cyfrę kontrolną do 12 cyfr kodu kreskowego. wagi 1 i 3i % 2(10 − suma % 10) % 10string Rozwiąż 14 Zera na końcu silniśrednie✓ zaliczone Ile zer kończy liczbę n! dla n do 10¹⁸? Licz piątki, nie silnię. n / 5 + n / 25 + …whilelong long Rozwiąż 15 Lata przestępne — szybkośrednie✓ zaliczone Ile lat przestępnych jest od a do b, gdy przedział ma 10¹⁸ lat? y / 4 − y / 100 + y / 400f(b) − f(a − 1)long long Rozwiąż 16 Liczby szczęśliweśrednie✓ zaliczone Zastępuj liczbę sumą kwadratów cyfr. Dojdziesz do 1 czy do 4? cyfry: % 10 i / 10pętla w pętlilong long Rozwiąż 17 Zegar w lustrześrednie✓ zaliczone Godzina odczytana z lustra — która jest naprawdę? (720 − t) % 720zero → 12setw i setfill Rozwiąż 18 Grafik dyżurówśrednie✓ zaliczone Zsumuj czas dyżurów, z których część przechodzi przez północ. (koniec − start + 1440) % 1440suma/ 60 i % 60 Rozwiąż 19 Generator liczb pseudolosowychśrednie✓ zaliczone x → (a · x + c) mod m. Policz n-tą liczbę i ile było parzystych. (a * x + c) % mlong longlicznik Rozwiąż 20 Malowanie płotuśrednie✓ zaliczone Co a-ta sztacheta czerwona, co b-ta niebieska. Ile jakich — dla n do 10¹⁸? n / aNWWwłączanie i wyłączanielong long Rozwiąż
trudne

Trudne · zadania 21–29

Okresy reszt, IBAN, wyliczanka, ułamki okresowe i strefy czasowe — a na końcu wielki finał: dzień tygodnia dowolnej daty.

21 Dwie linie autobusowetrudne✓ zaliczone Rozkłady z przesunięciem. Kiedy oba autobusy odjadą razem — albo NIGDY? (t − s) % p == 0cykl resztzaokrąglanie w górę Rozwiąż 22 Ostatnia cyfra gigantatrudne✓ zaliczone a i n mają po 1000 cyfr. Jaka jest ostatnia cyfra aⁿ? cykl co 4n % 4 z napisua % 10 Rozwiąż 23 Numer konta IBANtrudne✓ zaliczone Sprawdź sumę kontrolną numeru konta: litery na liczby i modulo 97. modulo 97litery na liczbyreszta z olbrzymastring Rozwiąż 24 Wyliczankatrudne✓ zaliczone Co k-te dziecko w kółku odpada. Kto zostanie ostatni? w = (w + k) % inumeracja od 0Józef Flawiusz Rozwiąż 25 Ułamek okresowytrudne✓ zaliczone Zapisz a/b z okresem w nawiasie: 1/6 = 0.1(6), 1/7 = 0.(142857). dzielenie pisemneNWDczynniki 2 i 5powtórzona reszta Rozwiąż 26 Cyfra daleko po przecinkutrudne✓ zaliczone k-ta cyfra po przecinku a / b, gdy k sięga 10¹⁸. szybkie potęgowanie10ᵏ⁻¹ mod bdzielenie pisemne Rozwiąż 27 Lot przez strefy czasowetrudne✓ zaliczone Start, czas lotu i różnica stref. Jaki dzień i godzina przy lądowaniu? minuty od początku tygodnia% 10080liczby ujemnenazwy dni Rozwiąż 28 Kwadraty i resztytrudne✓ zaliczone Ile x od 1 do n (n do 10¹⁸) ma x² dające resztę r z dzielenia przez m? okresowość resztn / m pełnych okresówogon n % m Rozwiąż 29 Wielki finał: jaki to dzień tygodnia?trudne✓ zaliczone Dowolna data od 1583 do 9999 — jaki to dzień tygodnia? lata przestępnedni miesięcy% 7wszystko naraz Rozwiąż

Częste błędy i dobre praktyki

➖
Reszta ma znak liczby dzielonej
-7 % 3 to −1, a nie 2. Gdy potrzebujesz wyniku od 0 do n − 1, a liczba może być ujemna, użyj ((a % n) + n) % n.
🔢
Nieparzysta to != 0
Pisz x % 2 != 0, a nie x % 2 == 1 — dla ujemnych liczb nieparzystych reszta to −1. Parzystość przez == 0 działa zawsze.
💥
Nie dziel przez zero
a % 0 wysypuje program. Jeśli dzielnik pochodzi z wejścia i może być zerem, sprawdź go przez if (b == 0).
🚫
Tylko liczby całkowite
% nie działa na double — program się nie skompiluje. Przejdź na grosze, sekundy, centymetry albo użyj fmod.
⚖️
Kolejność działań
% liczy się jak * i /: przed + i -, a z mnożeniem od lewej do prawej. a + b % c to a + (b % c). W razie wątpliwości — nawias.
↔️
Kto przez kogo?
„a dzieli się przez b” to a % b == 0. Liczba, którą dzielimy, zawsze stoi po lewej stronie %.
1️⃣
Numeracja od 1
Przesunięcie w kółku numerowanym od 1: (x - 1 + k) % n + 1. Zwykłe (x + k) % n da 0, którego nie ma.
🔁
W cyklu liczy się reszta
Pełne doby, tygodnie i okrążenia niczego nie zmieniają. Zamiast symulować miliard kroków, weź t % długość_cyklu.
📏
Modulo po każdym kroku
Przy dużych wynikach bierz resztę po każdym dodawaniu i mnożeniu, a zmienne trzymaj w long long. Przepełnienie dzieje się przed % — potem już nic go nie naprawi.
✖️
w = w * i % MOD
A nie w *= i % MOD, które bierze resztę tylko z i. Odejmowanie modulo — z poprawką + MOD. Dzielenia modulo tak nie zrobisz.
0️⃣
Zero ma jedną cyfrę
Pętla while (n > 0) pominie liczbę 0. Gdy przechodzisz po cyfrach, a n może być zerem, użyj do … while.
⚡
NWD resztą, potęgi kwadratami
Euklides z % i szybkie potęgowanie robią w kilkudziesięciu krokach to, co zwykła pętla robiłaby latami.

Co dalej?

To była ostatnia lekcja pierwszego etapu — podstaw C++. Znasz już typy zmiennych, wejście i wyjście, instrukcje warunkowe, obie pętle i modulo: to wystarczy, żeby rozwiązywać pierwsze zadania olimpijskie. Następny etap zaczyna się od tablic — dzięki nim program zapamięta nie jedną liczbę, ale milion naraz. A jeśli chcesz trenować z mentorami — dołącz do T-Olimpians.