Co już umiesz i czego się nauczysz
Ta lekcja zakłada, że przerobiłeś wszystkie poprzednie: Typy zmiennych, Input / Output, If / Else, While loop, For loop, Modulo, Tablice, String, Pair, Vector, Sortowanie, Max / Min i Zaokrąglanie. Silnię już spotkałeś: w lekcji o pętli while policzyłeś 5!, w lekcji o modulo — silnię „modulo 10⁹ + 7”, a w lekcji o vectorze zobaczyłeś, że wszystkich permutacji n elementów jest właśnie n!.
Teraz poznasz silnię porządnie, od samego początku. Zobaczysz, dlaczego liczba ustawień to iloczyn kolejnych liczb, jak pętla liczy go krok po kroku i dlaczego zaczyna od jedynki. Potem przyjdą wielkie liczby: silnia rośnie tak szybko, że już 21! nie mieści się w żadnym zwykłym typie — a zadania i tak pytają o 100! albo o silnię miliona. Nauczysz się czterech sposobów, żeby sobie z tym poradzić, i zobaczysz, jak silnia pomaga liczyć sposoby: podia, drużyny, kody i trasy.
Uczymy się tak samo jak poprzednio. Przepisuj przykłady do swojego edytora i uruchamiaj je. Przy pytaniach „Co wypisze program?” najpierw policz w głowie albo na kartce — przy silni łatwo się pomylić o jedno mnożenie — a dopiero potem sprawdzaj odpowiedź. Po każdej części rób ćwiczenia w sprawdzarce i nie idź dalej, dopóki nie przestaną sprawiać Ci kłopotu — kolejne części budują na poprzednich.
Silnia i pętla
Ustawienia w kolejce, n! i 0! = 1, pętla krok po kroku i granice typów int i long long.
Tablica i modulo
Wszystkie silnie w tablicy, dzielenie silni, silnie cyfr, reszta z dzielenia silni i słynne 10⁹ + 7.
Zera i olbrzymy
Ile zer ma silnia na końcu, czynniki pierwsze silni, mnożenie pisemne w vectorze i liczba cyfr przez log10.
Liczenie sposobów
Podium, kody, uściski dłoni, symbol Newtona, trójkąt Pascala, anagramy i trasy na kratce.
int, a program nie ostrzeże Cię ani słowem — po prostu wypisze bzdurę. Zanim napiszesz pierwszą linijkę, zawsze zapytaj: jak duży może być wynik?
Mapa lekcji
Na ile sposobów można stanąć w kolejce?
Zacznijmy od zagadki, a nie od programu. Troje przyjaciół — Ala, Bartek i Celina — podchodzi do budki z lodami. Na ile różnych sposobów mogą ustawić się w kolejce? Dwa ustawienia uznajemy za różne, jeśli choć jedna osoba stoi w nich na innym miejscu.
Najprościej wypisać wszystkie możliwości. Oznaczmy przyjaciół literami A, B i C. Żeby niczego nie zgubić, wypisujemy po kolei: najpierw ustawienia, w których pierwsza stoi Ala, potem te z Bartkiem na początku, a na końcu te z Celiną.
| nr | 1. miejsce | 2. miejsce | 3. miejsce |
|---|---|---|---|
| 1 | A | B | C |
| 2 | A | C | B |
| 3 | B | A | C |
| 4 | B | C | A |
| 5 | C | A | B |
| 6 | C | B | A |
Wyszło 6 ustawień. Zauważ, że każda osoba jest na początku kolejki dokładnie dwa razy — bo gdy pierwsze miejsce jest już zajęte, dwie pozostałe osoby mogą ustawić się za nią na dwa sposoby.
A ile ustawień ma czwórka przyjaciół? Albo piątka? Sprawdź w ustawiarce poniżej — wybierz liczbę osób, a zobaczysz wszystkie możliwe kolejki. Zanim klikniesz 4 i 5, spróbuj zgadnąć, ile ich będzie.
Drzewko wyborów — liczenie bez wypisywania
Wypisywanie działa dla trzech osób, ale dla dziesięciu ustawień są miliony. Policzmy sprytniej. Ustawiamy kolejkę miejsce po miejscu:
• na pierwsze miejsce może stanąć każda z 3 osób,
• gdy pierwsze miejsce jest zajęte, na drugie zostają już tylko 2 osoby,
• na trzecie miejsce zostaje 1 osoba — ta, która jeszcze nie stoi.
Każdy wybór pierwszej osoby łączy się z każdym wyborem drugiej, więc możliwości mnożymy: 3 · 2 · 1 = 6. Na rysunku każda ścieżka od góry do dołu to jedno ustawienie — policz liście na dole.
To samo rozumowanie działa dla dowolnej liczby osób. Dla czterech: na pierwsze miejsce 4 możliwości, na drugie 3, na trzecie 2, na ostatnie 1 — razem 4 · 3 · 2 · 1 = 24. Dla pięciu: 5 · 4 · 3 · 2 · 1 = 120. Dokładnie tyle pokazała ustawiarka.
Definicja: n silnia
Iloczyn wszystkich liczb całkowitych od 1 do n nazywamy silnią liczby n i zapisujemy z wykrzyknikiem: n! (czytamy: „n silnia”). Kolejność mnożenia nie ma znaczenia, więc 4 · 3 · 2 · 1 to to samo co 1 · 2 · 3 · 4.
| n | n! jako iloczyn | n! |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 1 · 2 | 2 |
| 3 | 1 · 2 · 3 | 6 |
| 4 | 1 · 2 · 3 · 4 | 24 |
| 5 | 1 · 2 · 3 · 4 · 5 | 120 |
| 6 | 1 · 2 · … · 6 | 720 |
| 7 | 1 · 2 · … · 7 | 5 040 |
| 8 | 1 · 2 · … · 8 | 40 320 |
| 9 | 1 · 2 · … · 9 | 362 880 |
| 10 | 1 · 2 · … · 10 | 3 628 800 |
Popatrz na prawą kolumnę. Do 5! liczby są małe i przyjazne. Potem zaczyna się wyścig: 7! to już ponad pięć tysięcy, a 10! — ponad trzy i pół miliona.
Dziesięć osób może więc ustawić się w kolejce na 3 628 800 sposobów. Gdyby co sekundę zmieniać ustawienie, przejście przez wszystkie zajęłoby dokładnie sześć tygodni, bez przerwy na sen.
W części 3 zobaczysz, że ten wyścig szybko staje się problemem dla komputera.
n! = 1 · 2 · 3 · … · n — iloczyn wszystkich liczb od 1 do n. To liczba sposobów, na które można ustawić n różnych rzeczy w rzędzie: ludzi w kolejce, książki na półce, litery w słowie. Wynika z drzewka wyborów: na pierwsze miejsce n możliwości, na drugie n − 1, …, na ostatnie 1.
Uwaga: w C++ nie ma znaku silni
cout << !5 << "\n";
cout << !0 << "\n";
cout << !1 + !1 << "\n";
Wykrzyknik w matematyce oznacza silnię, ale w C++ znaczy coś zupełnie innego — znasz go z lekcji o if: to zaprzeczenie („nie”). !5 to „nie prawda” (bo każda liczba różna od zera jest prawdą), czyli fałsz, wypisany jako 0. !0 to prawda, czyli 1.
Zapis 5! się nawet nie skompiluje. C++ nie ma gotowej silni — trzeba ją policzyć samemu, pętlą.
Każda silnia z poprzedniej
Spójrz jeszcze raz na tabelkę. 5! = 1 · 2 · 3 · 4 · 5, a 4! = 1 · 2 · 3 · 4. Czyli 5! to po prostu 4! pomnożone przez 5: 24 · 5 = 120. A 6! to 5! pomnożone przez 6: 120 · 6 = 720. Ogólnie:
n! = (n − 1)! · n — żeby dostać kolejną silnię, wystarczy poprzednią pomnożyć przez następną liczbę.
To najważniejsza obserwacja w całej lekcji. Dzięki niej jedna pętla, która mnoży zmienną kolejno przez 1, 2, 3, …, przechodzi przez wszystkie silnie po drodze:
int w = 1;
for (int n = 1; n <= 8; n++) {
w = w * n; // z (n-1)! robimy n!
cout << n << "! = " << w << "\n";
}
Przed pętlą w ma wartość 1. W pierwszym obrocie mnożymy przez 1 — wychodzi 1, czyli 1!. W drugim mnożymy przez 2 — wychodzi 2, czyli 2!. W trzecim przez 3 — 6, czyli 3!. I tak dalej.
Po obrocie z licznikiem n zmienna w trzyma dokładnie n!. Nie liczymy każdej silni od nowa — każdą robimy z poprzedniej jednym mnożeniem.
Dlaczego 0! = 1?
| silnia | z następnej | wynik |
|---|---|---|
| 4! | — | 24 |
| 3! | 4! / 4 = 24 / 4 | 6 |
| 2! | 3! / 3 = 6 / 3 | 2 |
| 1! | 2! / 2 = 2 / 2 | 1 |
| 0! | 1! / 1 = 1 / 1 | 1 |
Iloczyn liczb „od 1 do 0” brzmi dziwnie — nie ma tam żadnej liczby. Matematycy umówili się, że 0! = 1, i ta umowa ma sens z kilku stron naraz.
Po pierwsze: skoro n! = (n − 1)! · n, to idąc w dół, dzielimy: (n − 1)! = n! / n. Tabelka pokazuje, że w ten sposób dochodzimy do 0! = 1.
Po drugie: na ile sposobów można ustawić zero osób? Na jeden — pusta kolejka to jedno ustawienie.
Po trzecie: tak działa pętla. Gdy n = 0, pętla for (int i = 1; i <= n; i++) nie wykona się ani razu i w zmiennej zostaje wartość startowa — 1.
Pierwszy program z silnią
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int w = 1; // start od jedynki
for (int i = 1; i <= n; i++) {
w *= i; // w = w * i
}
cout << n << "! = " << w << "\n";
return 0;
}
To cały program: wczytaj n, ustaw wynik na 1, pomnóż go przez każdą liczbę od 1 do n i wypisz.
W części 2 przejdziemy przez tę pętlę obrót po obrocie i zobaczymy, co się psuje, gdy zmienisz w niej choćby jeden znak. Na razie zapamiętaj trzy rzeczy:
• wynik startuje od 1, a nie od 0,
• licznik idzie od 1 do n włącznie (i <= n),
• typ int wystarcza tylko do 12! — dalej trzeba większego „pudełka”.
Ustawienia z warunkami
W zadaniach rzadko pytają o same ustawienia. Zwykle jest jakiś warunek: ktoś stoi na ustalonym miejscu, ktoś chce stać obok kogoś, a stół jest okrągły. Za każdym razem pomaga to samo drzewko wyborów — trzeba tylko dobrze policzyć, ile możliwości jest na każdym etapie.
Ola stoi pierwsza. W kolejce jest n osób, ale Ola przyszła pierwsza i jej miejsce jest pewne. Ustawiamy tylko pozostałe n − 1 osób: (n − 1)! sposobów. Dla n = 4 to 3! = 6.
Dwie półki. Na górnej półce stoją 2 książki, na dolnej 3 inne, a książki nie zmieniają półek. Górną półkę ułożysz na 2! = 2 sposoby, dolną na 3! = 6, a każdy układ górnej pasuje do każdego układu dolnej: 2 · 6 = 12.
Okrągły stół. Czterech rycerzy siada przy okrągłym stole, a rozsadzenia, które różnią się tylko obrotem stołu, są takie same. Posadź pierwszego rycerza gdziekolwiek — przy okrągłym stole wszystkie miejsca są równe. Pozostali trzej siadają na 3! = 6 sposobów. Ogólnie (n − 1)!.
Ala i Bartek obok siebie. „Sklej” ich w jedną parę — wtedy ustawiasz n − 1 elementów: (n − 1)! sposobów. W środku pary są jeszcze 2 możliwości: AB albo BA.
int n = 4; // osoby: A, B, C, D
int w = 1;
for (int i = 1; i <= n - 1; i++) {
w *= i; // (n-1)! — para liczy się jak jedna osoba
}
cout << 2 * w << "\n"; // razy 2: AB albo BA
Dla czterech osób: para AB (albo BA) i osoby C, D to trzy „elementy”, które ustawiamy na 3! = 6 sposobów. Razy dwa kierunki pary: 12.
Sprawdź to wypisując: ABCD, ABDC, CABD, DABC, CDAB, DCAB i sześć takich samych z BA zamiast AB. Zgadza się — 12.
Najpierw policz w głowie — wypisz sobie na kartce kolejne iloczyny — a dopiero potem kliknij „Pokaż odpowiedź”.
int w = 1;
for (int i = 1; i <= 4; i++) w *= i;
cout << w;
Pokaż odpowiedź
int w = 1;
for (int i = 1; i <= 3; i++) w *= i;
cout << w * w;
Pokaż odpowiedź
int w = 1;
for (int i = 1; i <= 0; i++) w *= i;
cout << w;
Pokaż odpowiedź
cout << !5 + !0;
Pokaż odpowiedź
int w = 1;
for (int i = 1; i <= 6; i++) w *= i;
cout << w / 120;
Pokaż odpowiedź
int n = 5, w = 1;
for (int i = 1; i <= n - 1; i++) w *= i;
cout << w;
Pokaż odpowiedź
int w = 1;
for (int i = 1; i <= 3; i++) w *= i;
int v = 1;
for (int i = 1; i <= w; i++) v *= i;
cout << v;
Pokaż odpowiedź
int w = 1;
for (int i = 2; i <= 4; i++) w *= i;
cout << 2 * w;
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ę.
Silnia w pętli — obrót po obrocie
Pętla, która liczy silnię, ma tylko trzy linijki. Właśnie dlatego łatwo w niej o błąd — jeden zły znak i wynik jest zupełnie inny. W tej części przejdziemy przez nią powoli, obrót po obrocie, a potem zobaczymy, co dzieje się po zmianie startu, warunku albo kierunku. Na koniec pokażę Ci kilka „krewnych” silni: iloczyn od a do b, silnię podwójną i sumę silni.
Prześledźmy pętlę
Oto pętla z części 1, tym razem z wynikiem w long long (dlaczego — zobaczysz w części 3). Kliknij Krok i patrz, która linijka właśnie się wykonuje i jak zmieniają się zmienne. Możesz też wybrać inne n — spróbuj koniecznie n = 0 i n = 1.
| i | w po w *= i |
|---|
| obrót | i | i <= 5? | w przed | w po w *= i |
|---|---|---|---|---|
| 1 | 1 | tak | 1 | 1 |
| 2 | 2 | tak | 1 | 2 |
| 3 | 3 | tak | 2 | 6 |
| 4 | 4 | tak | 6 | 24 |
| 5 | 5 | tak | 24 | 120 |
| — | 6 | nie | koniec pętli | |
To tabelka śladu dla n = 5. Każdy wiersz to jeden obrót: najpierw sprawdzamy warunek, potem mnożymy, potem licznik rośnie o 1.
Pętla wykonała się dokładnie 5 razy, dla i = 1, 2, 3, 4, 5. Po piątym obrocie i zrobiło się równe 6, warunek 6 <= 5 jest fałszywy i pętla się kończy. W zmiennej w zostaje 120, czyli 5!.
Zauważ, że w kolumnie „w po” po kolei pojawiają się 1!, 2!, 3!, 4! i 5! — dokładnie tak, jak obiecywała obserwacja n! = (n − 1)! · n.
Start od jedynki, nie od zera
int n = 5;
long long w = 0; // BŁĄD: start od zera
for (int i = 1; i <= n; i++) {
w *= i;
}
cout << w << "\n";
Przy liczeniu sumy zaczynamy od 0, bo dodanie zera niczego nie zmienia. Przy liczeniu iloczynu zaczynamy od 1, bo to mnożenie przez jedynkę niczego nie zmienia.
Zero pomnożone przez cokolwiek daje zero: 0 · 1 = 0, 0 · 2 = 0, … — wynik zostaje zerem na zawsze. To jeden z najczęstszych błędów w zadaniach z silnią i łatwo go przeoczyć, bo program nie zgłasza żadnego błędu.
Warunek i <= n, a nie i < n
int n = 5;
long long w = 1;
for (int i = 1; i < n; i++) { // BŁĄD: < zamiast <=
w *= i;
}
cout << w << "\n";
Z warunkiem i < n pętla zatrzymuje się, zanim pomnoży przez samo n. Dla n = 5 mnoży tylko przez 1, 2, 3 i 4 — i wypisuje 4! = 24 zamiast 120.
To błąd „o jeden”, znany z lekcji o pętlach. Najprostszy sposób, żeby go wyłapać: sprawdź program dla małego n, którego silnię znasz na pamięć (3! = 6, 5! = 120).
Od jedynki czy od dwójki?
int n = 5;
long long w = 1;
for (int i = 2; i <= n; i++) { // mnożenie przez 1 pomijamy
w *= i;
}
cout << w << "\n";
Mnożenie przez 1 niczego nie zmienia, więc pętla może równie dobrze zaczynać się od 2. Wynik jest ten sam, a obrotów o jeden mniej.
Dla n = 0 i n = 1 taka pętla nie wykona się ani razu (bo 2 <= 0 i 2 <= 1 to fałsz) i zostanie 1 — dobrze, bo 0! = 1! = 1. Obie wersje są poprawne; wybierz tę, która mniej Cię myli.
Liczby ujemne — pętla tu nie pomoże
int n;
cin >> n;
if (n < 0) {
cout << "BRAK\n"; // silnia liczby ujemnej nie istnieje
} else {
long long w = 1;
for (int i = 1; i <= n; i++) w *= i;
cout << w << "\n";
}
Silnia jest określona tylko dla liczb n ≥ 0. Co zrobi zwykła pętla dla n = −3? Warunek 1 <= −3 jest fałszywy, więc pętla nie wykona się ani razu i program wypisze 1. Wygląda niewinnie, ale to nieprawda — −3! nie wynosi 1, po prostu nie istnieje.
Dlatego, jeśli w zadaniu mogą pojawić się liczby ujemne, trzeba je wyłapać osobnym if-em przed pętlą.
Pętla w dół i pętla while
int n = 5;
long long w = 1;
for (int i = n; i >= 1; i--) {
w *= i; // 5 · 4 · 3 · 2 · 1
}
cout << w << "\n";
int n = 5;
long long w = 1;
int i = 1;
while (i <= n) {
w *= i;
i++;
}
cout << w << "\n";
Kolejność mnożenia nie ma znaczenia, więc pętla może iść od n w dół do 1 — tak zresztą liczyliśmy w drzewku wyborów (5 możliwości, potem 4, potem 3…). Wersja z while robi dokładnie to samo co for, tylko start, warunek i krok są w trzech różnych miejscach — tak jak w lekcji o pętli while.
Pętla w dół przydaje się, gdy chcesz wypisać iloczyn od największej liczby: 5 * 4 * 3 * 2 * 1 = 120.
Kilka silni naraz — nie zapomnij o resecie
int t;
cin >> t;
long long w = 1; // BŁĄD: tylko raz, przed pętlą
for (int k = 0; k < t; k++) {
int n;
cin >> n;
for (int i = 1; i <= n; i++) w *= i;
cout << w << "\n";
}
int t;
cin >> t;
for (int k = 0; k < t; k++) {
int n;
cin >> n;
long long w = 1; // dobrze: od nowa dla każdej liczby
for (int i = 1; i <= n; i++) w *= i;
cout << w << "\n";
}
Gdy program liczy silnię dla kilku liczb, wynik trzeba ustawiać na 1 dla każdej liczby osobno. W lewym programie w pamięta wynik poprzedniej liczby: dla drugiej liczby mnoży 6 · 1 · 2 = 12 zamiast 1 · 1 · 2 = 2, a dla trzeciej — 12 · 24 = 288.
Zasada jest prosta: zmienna, która ma zaczynać „od zera” (albo od jedynki) dla każdej liczby, musi być ustawiana wewnątrz pętli po liczbach.
Iloczyn od a do b
int a = 5, b = 7;
long long w = 1;
for (int i = a; i <= b; i++) {
w *= i; // 5 · 6 · 7
}
cout << w << "\n";
Silnia to iloczyn od 1 do n. Gdy pętla zaczyna się od innej liczby a, dostajemy iloczyn kolejnych liczb od a do b: 5 · 6 · 7 = 210.
Ten iloczyn to „kawałek” silni: 7! = (1 · 2 · 3 · 4) · (5 · 6 · 7) = 4! · 210, więc 210 = 7! / 4!. Ogólnie iloczyn od a do b to b! / (a − 1)!. Ale tak go nie licz — gdy b jest duże, b! nie zmieści się w żadnym typie, a sam iloczyn od a do b może być całkiem mały (na przykład 999 · 1000).
Co druga liczba: silnia podwójna
int n = 7;
long long w = 1;
for (int i = n; i >= 1; i -= 2) {
w *= i; // 7 · 5 · 3 · 1
}
cout << w << "\n";
n = 8;
w = 1;
for (int i = n; i >= 1; i -= 2) {
w *= i; // 8 · 6 · 4 · 2
}
cout << w << "\n";
Silnia podwójna n!! to iloczyn co drugiej liczby, od n w dół. Dla nieparzystego n mnożymy liczby nieparzyste: 7!! = 7 · 5 · 3 · 1 = 105. Dla parzystego — parzyste: 8!! = 8 · 6 · 4 · 2 = 384. Umowa: 0!! = 1.
Wystarczy zmienić krok pętli: i -= 2 zamiast i--. Pętla sama zatrzyma się na 1 albo na 2.
Uwaga: n!! to nie (n!)! — silnia podwójna jest dużo mniejsza od zwykłej silni. W bazie zadań zobaczysz, że silnia podwójna liczy, na ile sposobów można podzielić uczniów na pary.
Suma silni — każda z poprzedniej
int n = 4;
long long suma = 0;
for (int k = 1; k <= n; k++) {
long long w = 1; // k! liczone od nowa
for (int i = 1; i <= k; i++) w *= i;
suma += w;
}
cout << suma << "\n";
int n = 4;
long long s = 1, suma = 0;
for (int i = 1; i <= n; i++) {
s *= i; // teraz s to i!
suma += s;
}
cout << suma << "\n";
1! + 2! + 3! + 4! = 1 + 2 + 6 + 24 = 33. Oba programy liczą to samo, ale inaczej. Lewy dla każdego k liczy k! od nowa — pętla w pętli. Prawy korzysta z tego, że każda silnia powstaje z poprzedniej: jedna pętla i dwie zmienne — s trzyma bieżącą silnię, a suma zbiera wynik.
Dla n = 20 lewy program wykona 210 mnożeń, a prawy — 20. Przy silniach to jeszcze bez znaczenia, ale ten sam pomysł („nie licz od nowa, tylko popraw poprzedni wynik”) wróci w wielu zadaniach, gdzie oszczędzi Ci miliony operacji.
Podobnie policzysz sumę z naprzemiennymi znakami, 1! − 2! + 3! − 4! + …: po s *= i dodaj s, gdy i jest nieparzyste (i % 2 == 1), a odejmij, gdy parzyste.
Najpierw odpowiedz w myślach — wypisz sobie na kartce kolejne wartości zmiennych — a dopiero potem kliknij „Pokaż odpowiedź”.
long long w = 1;
for (int i = 1; i <= 6; i++) w *= i;
cout << w;
Pokaż odpowiedź
long long w = 1;
for (int i = 1; i < 6; i++) w *= i;
cout << w;
Pokaż odpowiedź
long long w = 1;
for (int i = 3; i <= 5; i++) w *= i;
cout << w;
Pokaż odpowiedź
long long w = 1;
for (int i = 9; i >= 1; i -= 2) w *= i;
cout << w;
Pokaż odpowiedź
long long w = 1;
for (int i = 6; i >= 1; i -= 2) w *= i;
cout << w;
Pokaż odpowiedź
long long s = 1, suma = 0;
for (int i = 1; i <= 3; i++) {
s *= i;
suma += s;
}
cout << suma;
Pokaż odpowiedź
int n = -2;
long long w = 1;
for (int i = 1; i <= n; i++) w *= i;
cout << w;
Pokaż odpowiedź
int ile = 0;
for (int i = 2; i <= 10; i++) ile++;
cout << ile;
Pokaż odpowiedź
long long s = 1, w = 0;
for (int i = 1; i <= 4; i++) {
s *= i;
if (i % 2 == 1) w += s;
else w -= s;
}
cout << w;
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ę.
Jak szybko rośnie silnia — i gdzie pęka typ
Silnia jest prosta w liczeniu, ale ma jedną ogromną wadę: rośnie szybciej niż prawie wszystko, co znasz. Już 13! nie mieści się w int, a 21! — w long long. W tej części zobaczysz, jak wygląda moment „pęknięcia”, dlaczego program o nim nie mówi i jak pisać pętle, które zatrzymują się, zanim do niego dojdzie.
Wyścig: silnia kontra inne liczby
| n | n · n | 2ⁿ | n! |
|---|---|---|---|
| 1 | 1 | 2 | 1 |
| 3 | 9 | 8 | 6 |
| 5 | 25 | 32 | 120 |
| 10 | 100 | 1 024 | 3 628 800 |
| 15 | 225 | 32 768 | ≈ 1,3 · 10¹² |
| 20 | 400 | 1 048 576 | ≈ 2,4 · 10¹⁸ |
| 52 | 2 704 | ≈ 4,5 · 10¹⁵ | ≈ 8,1 · 10⁶⁷ |
Na początku silnia jest nawet mniejsza od 2ⁿ. Ale potęga dwójki w każdym kroku mnoży się tylko przez 2, a silnia — przez coraz większe liczby: przez 10, przez 15, przez 20… Od n = 4 silnia prowadzi i już nigdy nie odda prowadzenia.
Ostatni wiersz to talia 52 kart. Liczba jej ułożeń ma 68 cyfr. To tak dużo, że gdy dobrze potasujesz karty, prawie na pewno trzymasz w ręku ułożenie, którego nikt na świecie jeszcze nigdy nie miał.
Przesuwaj suwak i patrz, w którym miejscu silnia przestaje mieścić się w typach C++. Pod każdym typem widać, co wypisałby program, który liczy silnię w tym typie — na zielono, gdy wynik jest prawdziwy, na czerwono, gdy to już bzdura.
int pęka po 12!
int w = 1;
for (int i = 1; i <= 17; i++) {
w *= i;
if (i >= 11) cout << i << "! = " << w << "\n";
}
Typ int mieści liczby do około 2,1 miliarda (dokładnie 2 147 483 647). 12! = 479 001 600 jeszcze się mieści. Prawdziwe 13! to 6 227 020 800 — prawie trzy razy więcej niż granica.
Program nie zgłasza błędu. Liczba „przekręca się” jak licznik kilometrów (lekcja o typach) i wychodzi 1 932 053 504 — wygląda całkiem wiarygodnie! Dalej jest jeszcze gorzej: 14! wychodzi mniejsze od 13!, a 17! — ujemne.
Silnia nigdy nie maleje i nigdy nie jest ujemna. Jeśli widzisz coś takiego, to pewny znak przepełnienia.
long long pęka po 20!
long long w = 1;
for (int i = 1; i <= 22; i++) {
w *= i;
if (i >= 19) cout << i << "! = " << w << "\n";
}
long long mieści liczby do około 9,2 · 10¹⁸. 20! ≈ 2,4 · 10¹⁸ jeszcze się mieści, a 21! ≈ 5,1 · 10¹⁹ — już nie, i od razu wychodzi liczba ujemna.
Nawet unsigned long long, który sięga 1,8 · 10¹⁹, nie pomoże — 21! jest od niego prawie trzy razy większe. Każdy zwykły typ całkowity kończy się na 20!.
int mieści silnie do 12! = 479 001 600, a long long — do 20! = 2 432 902 008 176 640 000. Powyżej wynik jest bzdurą, choć program nie zgłosi błędu. Dlatego jeśli w zadaniu n może być większe niż 20, to zadanie na pewno nie każe wypisać całej silni zwykłą pętlą — pyta o coś innego: o resztę z dzielenia, o zera na końcu, o liczbę cyfr albo o cyfry zapisane w tablicy. Tym wszystkim zajmiemy się w częściach 5–7.
Sprawdź, zanim pomnożysz
Często nie trzeba liczyć całej silni — wystarczy wiedzieć, czy przekroczy jakąś granicę x. Na przykład: jaka jest największa silnia, która nie przekracza 10¹⁸? Kusi, żeby mnożyć, aż w > x. Ale jeśli x jest bliskie granicy typu, to ostatnie mnożenie samo może się przepełnić, zanim zdążysz cokolwiek porównać.
Sztuczka: zamiast sprawdzać po mnożeniu, czy w * i > x, sprawdzamy przed mnożeniem, czy w > x / i. Dla liczb dodatnich to ten sam warunek (dzielenie całkowite niczego tu nie psuje), a x / i nigdy się nie przepełni.
long long x = 1000000000000000000LL; // 10^18
long long w = 1;
int n = 1;
while (w <= x / (n + 1)) { // czy (n+1)! = w·(n+1) zmieści się w x?
n++;
w *= n;
}
cout << n << "! = " << w << "\n";
W każdym obrocie pytamy: czy następna silnia, czyli w · (n + 1), nadal jest ≤ x? Zamiast mnożyć, porównujemy w z x / (n + 1).
Dla n = 19: w = 19! ≈ 1,2 · 10¹⁷, a x / 20 = 5 · 10¹⁶. Warunek jest fałszywy — 20! przekroczyłoby 10¹⁸ — więc pętla się kończy. Wynik: 19!.
Tę samą sztuczkę znasz z lekcji o typach przy mnożeniu dużych liczb. Przyda się zawsze, gdy iloczyn może „uciec” poza typ.
Czy n! przekracza x — nawet dla n = 10⁹
long long n, x;
cin >> n >> x;
long long w = 1;
bool wieksza = false;
for (long long i = 2; i <= n; i++) {
if (w > x / i) { // w · i > x
wieksza = true;
break; // dalej już tylko rośnie
}
w *= i;
}
if (w > x) wieksza = true;
cout << (wieksza ? "TAK" : "NIE") << "\n";
Silnia miliarda ma miliardy cyfr — nikt jej nie policzy. Ale żeby odpowiedzieć, czy jest większa od 10¹⁸, wystarczy kilkanaście mnożeń: przy i = 20 warunek w > x / i staje się prawdziwy, a break kończy pętlę. Dalsze mnożenie tylko zwiększałoby wynik, więc odpowiedź jest już pewna.
Dla n = 5 i x = 120 pętla dochodzi do końca, w = 120, a 120 > 120 to fałsz — więc NIE.
Zwróć uwagę na long long i: licznik może dojść do 10⁹, a x / i liczymy na long long.
W drugą stronę: czy liczba jest silnią?
long long x;
cin >> x;
long long w = 1;
int n = 0;
while (w < x) { // szukamy silni ≥ x
n++;
w *= n;
}
if (w == x) cout << x << " = " << n << "!\n";
else cout << "NIE\n";
Liczymy kolejne silnie od 0! = 1, dopóki są mniejsze od x. Gdy pętla się zatrzyma, w jest pierwszą silnią ≥ x. Wystarczy sprawdzić, czy trafiliśmy dokładnie.
Dla 100: kolejne silnie to 1, 1, 2, 6, 24, 120 — z 24 przeskakujemy od razu na 120 i omijamy 100. Silnie rosną, więc dalej szukać nie ma sensu: 100 nie jest silnią.
Dla x = 1 pętla nie wykona się ani razu i wypisze 0!, bo 0! = 1 (to samo co 1!, ale 0 jest mniejsze).
Ile cyfr ma silnia?
long long w = 1;
for (int i = 1; i <= 20; i++) {
w *= i;
if (i % 5 == 0) {
string s = to_string(w);
cout << i << "! ma " << s.size() << " cyfr\n";
}
}
Dopóki silnia mieści się w long long, cyfry policzysz jak każdej innej liczby: zamieniając ją na napis (to_string z lekcji o napisach) albo pętlą z w /= 10 (lekcja o pętli while).
Każde mnożenie przez liczbę dwucyfrową dokłada silni jedną albo dwie cyfry. W części 7 zobaczysz, jak policzyć cyfry silni miliona — bez liczenia samej silni.
A gdyby tak double?
double w = 1;
for (int i = 1; i <= 171; i++) {
w *= i;
if (i == 20 || i == 25 || i == 170 || i == 171) {
cout << i << "! = " << w << "\n";
}
}
Typ double sięga aż do około 10³⁰⁸, więc mieści nawet 170!. Haczyk: pamięta tylko około 15–16 pierwszych cyfr liczby, a resztę zaokrągla (pamiętasz z lekcji o zaokrąglaniu?). 25! ma 26 cyfr — double zna tylko początek.
Do zadań, w których trzeba podać silnię dokładnie, double się nie nadaje. Za to w części 7 użyjemy go sprytnie — do liczenia cyfr i pierwszej cyfry olbrzymiej silni. A 171! nie mieści się już nawet w double: program wypisuje inf — nieskończoność.
Najpierw odpowiedz w myślach — wypisz sobie na kartce kolejne wartości zmiennych — a dopiero potem kliknij „Pokaż odpowiedź”.
long long w = 1;
for (int i = 1; i <= 12; i++) w *= i;
cout << w / 11 / 12;
Pokaż odpowiedź
int w = 1;
for (int i = 1; i <= 13; i++) w *= i;
cout << (w > 479001600 ? "wieksze" : "mniejsze");
Pokaż odpowiedź
long long x = 1000;
long long w = 1;
int n = 1;
while (w <= x / (n + 1)) {
n++;
w *= n;
}
cout << n;
Pokaż odpowiedź
long long x = 24, w = 1;
int n = 0;
while (w < x) {
n++;
w *= n;
}
cout << n << " " << (w == x);
Pokaż odpowiedź
long long w = 1;
for (int i = 1; i <= 10; i++) w *= i;
cout << to_string(w).size();
Pokaż odpowiedź
long long x = 100, w = 1;
int ile = 0;
for (long long i = 2; i <= 1000000000; i++) {
if (w > x / i) break;
w *= i;
ile++;
}
cout << ile;
Pokaż odpowiedź
double w = 1;
for (int i = 1; i <= 15; i++) w *= i;
cout << w;
Pokaż odpowiedź
int n = 20;
if (n <= 12) cout << "int";
else if (n <= 20) cout << "long long";
else cout << "za duzo";
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ę.
Tablica silni — policz raz, korzystaj wiele razy
Silnie, które mieszczą się w long long, są tylko 21: od 0! do 20!. Skoro jest ich tak mało, a każda powstaje z poprzedniej jednym mnożeniem, to najwygodniej policzyć je wszystkie raz, na samym początku programu, i włożyć do tablicy. Potem każda silnia jest „od ręki” — wystarczy zajrzeć do pudełka z odpowiednim numerem. W tej części zobaczysz, co jeszcze daje taka tablica: dzielenie silni, silnie cyfr, łańcuchy liczb i nowy system liczbowy.
Tablica f: f[i] = i!
long long f[21];
f[0] = 1; // 0! = 1
for (int i = 1; i <= 20; i++) {
f[i] = f[i - 1] * i; // i! = (i-1)! · i
}
cout << f[5] << " " << f[10] << " " << f[20] << "\n";
To ta sama obserwacja co w części 1 — n! = (n − 1)! · n — tylko teraz zapisujemy każdą silnię do osobnego pudełka tablicy. Pudełko f[i] trzyma i!.
Tablica ma 21 pudełek (numery od 0 do 20), bo 21! i tak by się nie zmieściło. f[0] trzeba ustawić ręcznie przed pętlą — to „nasiono”, z którego wyrastają wszystkie pozostałe.
To bardzo podobne do sum prefiksowych z lekcji o tablicach: tam każde pudełko było sumą poprzedniego i kolejnej liczby, tu jest iloczynem.
Wiele pytań — jedna tablica
long long f[21];
f[0] = 1;
for (int i = 1; i <= 20; i++) f[i] = f[i - 1] * i;
int q;
cin >> q;
for (int k = 0; k < q; k++) {
int n;
cin >> n;
cout << f[n] << "\n"; // od ręki, bez pętli
}
Najpierw tablica, potem pytania. Każde pytanie to jedno zajrzenie do tablicy — nie ma pętli, nie ma ryzyka, że zapomnisz ustawić wynik na 1.
Dla 21 silni to jeszcze drobna oszczędność. Ale w części 5 ten sam pomysł posłuży do tablicy miliona reszt z dzielenia — tam liczenie każdej silni od nowa przy każdym pytaniu trwałoby zdecydowanie za długo.
Silnia przez silnię — bez liczenia silni
Ile to jest 7! / 5!? Można policzyć obie silnie i podzielić: 5040 / 120 = 42. Ale popatrz, co się dzieje w środku:
7! / 5! = (1 · 2 · 3 · 4 · 5 · 6 · 7) / (1 · 2 · 3 · 4 · 5) = 6 · 7 = 42.
Wszystkie czynniki od 1 do 5 skracają się i zostaje iloczyn liczb od 6 do 7. Ogólnie: n! / k! = (k + 1) · (k + 2) · … · n, dla k ≤ n. Dzielenie zawsze wychodzi bez reszty.
long long f[21];
f[0] = 1;
for (int i = 1; i <= 20; i++) f[i] = f[i - 1] * i;
cout << f[7] / f[5] << "\n"; // z tablicy
long long n = 1000, k = 998, w = 1;
for (long long i = k + 1; i <= n; i++) w *= i;
cout << w << "\n"; // 1000! / 998! = 999 · 1000
Dopóki obie silnie mieszczą się w tablicy, możesz po prostu podzielić f[n] / f[k].
Ale 1000! / 998! policzysz tylko drugim sposobem: 1000! ma 2568 cyfr i nie zmieści się nigdzie, a iloraz to zwyczajne 999 · 1000 = 999 000. Pętla od k + 1 do n — iloczyn od a do b z części 2.
Silnie cyfr: 145 = 1! + 4! + 5!
Mała tablica silni cyfr — od 0! do 9! — pozwala łatwo policzyć sumę silni cyfr dowolnej liczby. Dla 145 to 1! + 4! + 5! = 1 + 24 + 120 = 145 — wyszła ta sama liczba! Takich liczb, równych sumie silni swoich cyfr, jest tylko cztery: 1, 2, 145 i 40 585.
int f[10];
f[0] = 1;
for (int i = 1; i <= 9; i++) f[i] = f[i - 1] * i;
int x;
cin >> x;
int y = x, suma = 0;
while (y > 0) {
suma += f[y % 10]; // silnia ostatniej cyfry
y /= 10; // usuń ostatnią cyfrę
}
cout << suma << (suma == x ? " TAK" : " NIE") << "\n";
Cyfry wyciągamy tak jak w lekcji o modulo: y % 10 to ostatnia cyfra, a y /= 10 ją usuwa. Silnię każdej cyfry bierzemy prosto z tablicy f.
Dla 2022: 2! + 0! + 2! + 2! = 2 + 1 + 2 + 2 = 7. Zwróć uwagę na zero — 0! = 1, a nie 0!
Pułapka: dla x = 0 pętla while (y > 0) nie wykona się ani razu, a liczba 0 ma przecież jedną cyfrę, której silnia to 1. Gdy w zadaniu może pojawić się zero, wczytaj liczbę jako napis i przejdź po znakach.
Łańcuchy silni cyfr
int f[10];
f[0] = 1;
for (int i = 1; i <= 9; i++) f[i] = f[i - 1] * i;
int x = 69;
vector<int> byly;
while (find(byly.begin(), byly.end(), x) == byly.end()) {
byly.push_back(x);
cout << x << " -> ";
int y = x, suma = 0;
while (y > 0) {
suma += f[y % 10];
y /= 10;
}
x = suma;
}
cout << x << " (powtórka)\n";
Co się stanie, gdy sumę silni cyfr policzymy jeszcze raz, i jeszcze raz? Z 69 robi się 6! + 9! = 720 + 362 880 = 363 600, z tego 1454, potem 169… aż w końcu wraca liczba, którą już widzieliśmy, i od tej chwili wszystko kręci się w kółko.
Żeby zauważyć powtórkę, zapisujemy odwiedzone liczby w vectorze i przed każdym krokiem sprawdzamy find-em (lekcja o vectorze), czy bieżąca liczba już tam jest.
System silniowy
W lekcji o modulo zapisywałeś liczby w systemie dwójkowym: każda cyfra mówiła, ile razy bierzemy kolejną potęgę dwójki. Silnie też mogą być takimi „wagami”. Każdą liczbę da się zapisać jednoznacznie jako sumę
x = c_k · k! + … + c₂ · 2! + c₁ · 1!, gdzie każda cyfra c_i jest od 0 do i.
Na przykład 463 = 3 · 5! + 4 · 4! + 1 · 3! + 0 · 2! + 1 · 1! = 360 + 96 + 6 + 0 + 1. Cyfry liczymy jak przy wydawaniu reszty (lekcja o modulo): bierzemy największą silnię, która się mieści, dzielimy z resztą i resztę przekazujemy dalej.
long long f[21];
f[0] = 1;
for (int i = 1; i <= 20; i++) f[i] = f[i - 1] * i;
long long x = 463;
int k = 1;
while (k + 1 <= 20 && f[k + 1] <= x) k++; // największa silnia ≤ x
for (int i = k; i >= 1; i--) {
cout << x / f[i] << " "; // cyfra przy i!
x %= f[i]; // reszta idzie dalej
}
cout << "\n";
| i | x | x / i! | x % i! |
|---|---|---|---|
| 5 | 463 | 3 | 103 |
| 4 | 103 | 4 | 7 |
| 3 | 7 | 1 | 1 |
| 2 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |
Dlaczego cyfra przy i! nigdy nie przekracza i? Bo gdyby było (i + 1) · i!, to byłoby to (i + 1)! — i wzięlibyśmy tę większą silnię wcześniej. W bazie zadań zobaczysz, że ten system pozwala szybko znaleźć numer ustawienia w kolejności słownikowej.
long long silnia(int n) { if (n == 0) return 1; return silnia(n - 1) * n; } — funkcja, która woła samą siebie, aż dojdzie do 0! = 1. Na razie wystarczy Ci pętla i tablica: robią dokładnie to samo, tylko w drugą stronę — od 0! w górę.
Najpierw odpowiedz w myślach — wypisz sobie na kartce kolejne wartości zmiennych — a dopiero potem kliknij „Pokaż odpowiedź”.
long long f[21];
f[0] = 1;
for (int i = 1; i <= 20; i++) f[i] = f[i - 1] * i;
cout << f[8] / f[6];
Pokaż odpowiedź
long long f[21];
f[0] = 1;
for (int i = 1; i <= 20; i++) f[i] = f[i - 1] * i;
cout << f[3] + f[0];
Pokaż odpowiedź
long long w = 1;
for (long long i = 99; i <= 100; i++) w *= i;
cout << w;
Pokaż odpowiedź
int f[10];
f[0] = 1;
for (int i = 1; i <= 9; i++) f[i] = f[i - 1] * i;
cout << f[4] + f[0] + f[5] + f[8] + f[5];
Pokaż odpowiedź
int f[10];
f[0] = 1;
for (int i = 1; i <= 9; i++) f[i] = f[i - 1] * i;
int y = 100, suma = 0;
while (y > 0) {
suma += f[y % 10];
y /= 10;
}
cout << suma;
Pokaż odpowiedź
long long f[4] = {1, 1, 2, 6};
long long x = 10;
for (int i = 3; i >= 1; i--) {
cout << x / f[i];
x %= f[i];
}
Pokaż odpowiedź
long long f[21];
f[0] = 1;
for (int i = 1; i <= 20; i++) f[i] = f[i - 1] * i;
cout << f[20] / f[19];
Pokaż odpowiedź
int f[10];
f[0] = 1;
for (int i = 1; i <= 9; i++) f[i] = f[i - 1] * i;
cout << f[1] + f[4] + f[5];
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ę.
Silnia modulo — reszta bez liczenia całej silni
W zadaniach olimpijskich często pada zdanie: „wynik może być bardzo duży, więc wypisz jego resztę z dzielenia przez 10⁹ + 7”. Przy silni to zdanie jest ratunkiem: samej silni miliona nikt nie policzy, ale jej resztę z dzielenia — tak, i to w ułamku sekundy. W tej części przypomnisz sobie z lekcji o modulo, dlaczego wolno brać resztę po każdym kroku, i zobaczysz kilka sprytnych skrótów, w których silnia modulo daje się policzyć… bez żadnej pętli.
Ostatnia cyfra silni
| n | n! | ostatnia cyfra |
|---|---|---|
| 0 | 1 | 1 |
| 1 | 1 | 1 |
| 2 | 2 | 2 |
| 3 | 6 | 6 |
| 4 | 24 | 4 |
| 5 | 120 | 0 |
| 6 | 720 | 0 |
| 7 | 5 040 | 0 |
Ostatnia cyfra liczby to jej reszta z dzielenia przez 10. Dla małych n wystarczy policzyć silnię i wziąć % 10.
A od 5! w górę ostatnia cyfra to zawsze 0. Dlaczego? W iloczynie 1 · 2 · 3 · 4 · 5 · … są i dwójka, i piątka, a 2 · 5 = 10. Cała silnia dzieli się więc przez 10, a dalsze mnożenie już tego nie zmieni.
Wniosek: ostatnią cyfrę silni z n = 10¹⁸ znasz bez liczenia — to 0. Pętla do 10¹⁸ trwałaby setki lat.
Reszta po każdym kroku
Z lekcji o modulo pamiętasz najważniejszą zasadę: reszta z iloczynu zależy tylko od reszt czynników. Dlatego zamiast liczyć całą silnię, a dopiero na końcu brać resztę, możemy brać resztę po każdym mnożeniu: w = w * i % m. Liczby w środku pętli nigdy nie urosną ponad m · n, a wynik będzie dokładnie taki sam. Zobacz to na małym przykładzie: 6! mod 7.
int n = 6, m = 7;
long long w = 1;
for (int i = 1; i <= n; i++) {
w = w * i % m; // reszta po każdym mnożeniu
cout << "i = " << i << ": w = " << w << "\n";
}
| i | prawdziwe i! | i! % 7 | w · i % 7 |
|---|---|---|---|
| 3 | 6 | 6 | 2 · 3 % 7 = 6 |
| 4 | 24 | 3 | 6 · 4 % 7 = 3 |
| 5 | 120 | 1 | 3 · 5 % 7 = 1 |
| 6 | 720 | 6 | 1 · 6 % 7 = 6 |
Porównaj dwie środkowe kolumny: prawdziwe 4! = 24 daje resztę 3 z dzielenia przez 7, a program, który nigdy nie widział liczby 24, też ma w = 3 (bo 6 · 4 = 24, a 24 % 7 = 3). Dla 5!: 120 % 7 = 1 i w programie też 1. Zgadza się na każdym kroku.
Słynne 10⁹ + 7 — i dlaczego long long
const long long MOD = 1000000007;
long long w = 1;
for (long long i = 1; i <= 1000000; i++) {
w = w * i % MOD;
if (i == 20 || i == 1000000) cout << i << "! mod p = " << w << "\n";
}
Liczba 1 000 000 007 to ulubiona liczba autorów zadań: jest pierwsza i mieści się w int, a iloczyn dwóch reszt (każda mniejsza od niej) mieści się w long long.
Właśnie dlatego w musi być typu long long: reszta może być bliska miliardowi, a pomnożona przez i (nawet do miliona) daje do 10¹⁵. Gdyby w było typu int, iloczyn w * i przepełniłby się przed wzięciem reszty — i wynik byłby bzdurą, choć % MOD stoi na swoim miejscu.
Milion obrotów pętli to dla komputera ułamek sekundy.
Gdy n ≥ m, reszta to 0
long long n, m;
cin >> n >> m;
if (n >= m) {
cout << 0 << "\n"; // m jest jednym z czynników n!
} else {
long long w = 1;
for (long long i = 2; i <= n; i++) w = w * i % m;
cout << w << "\n";
}
Jeśli n ≥ m, to wśród czynników 1 · 2 · … · n jest samo m. Cała silnia dzieli się więc przez m i reszta to 0 — bez liczenia czegokolwiek.
Dopiero gdy n < m, trzeba liczyć — ale wtedy pętla ma mniej niż m obrotów. Jeśli m ≤ 10⁶, to nawet dla n = 10¹⁸ program kończy się błyskawicznie.
Uwaga: to działa tylko wtedy, gdy samo m jest jednym z czynników. Na przykład 4! = 24 dzieli się przez 8, choć 4 < 8 — więc 0 może wyjść też wcześniej, a pętla to i tak policzy.
Sumy i iloczyny modulo — ale nie dzielenie
const long long MOD = 1000000007;
int n = 20;
long long s = 1, suma = 0;
for (int i = 1; i <= n; i++) {
s = s * i % MOD; // s = i! mod p
suma = (suma + s) % MOD; // dodajemy i bierzemy resztę
}
cout << suma << "\n";
int m = 7;
int a = 120 % m, b = 6 % m; // 5! % 7 i 3! % 7
cout << a / b << "\n"; // ŹLE: 1 / 6
cout << 120 / 6 % m << "\n"; // dobrze: 20 % 7
Dodawanie i mnożenie „lubią” modulo — resztę można brać po każdym kroku. Lewy program liczy (1! + 2! + … + 20!) mod 10⁹ + 7 tak samo jak sumę silni z części 2, tylko z resztą po każdym działaniu.
Z dzieleniem tak się nie da, o czym ostrzegała już lekcja o modulo. Prawy program chce policzyć 5! / 3! = 20 modulo 7. Reszty to 1 i 6, a 1 / 6 = 0 — zupełnie co innego niż 20 % 7 = 6. Dlatego iloczyn od a do b modulo liczymy pętlą od a do b, a nie dzieleniem dwóch silni.
Tablica reszt na wiele pytań
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
long long f[1000001]; // duża tablica — poza main
int main() {
f[0] = 1;
for (int i = 1; i <= 1000000; i++) f[i] = f[i - 1] * i % MOD;
int q;
cin >> q;
for (int k = 0; k < q; k++) {
int n;
cin >> n;
cout << f[n] << "\n";
}
return 0;
}
Gdy pytań jest dużo, a każde dotyczy innego n do miliona, liczenie silni od nowa dla każdego pytania trwałoby za długo: tysiąc pytań razy milion mnożeń to miliard operacji.
Rozwiązanie znasz z części 4: tablica. Tym razem trzymamy w niej reszty: f[i] = i! mod p. Milion liczb long long to 8 MB — taką tablicę deklarujemy poza main, tak jak w lekcji o tablicach.
Ciekawostka: silnia rozpoznaje liczby pierwsze
| p | (p − 1)! | (p − 1)! % p | pierwsza? |
|---|---|---|---|
| 2 | 1 | 1 | tak |
| 3 | 2 | 2 | tak |
| 4 | 6 | 2 | nie |
| 5 | 24 | 4 | tak |
| 6 | 120 | 0 | nie |
| 7 | 720 | 6 | tak |
| 8 | 5 040 | 0 | nie |
| 11 | 3 628 800 | 10 | tak |
Spójrz na trzecią kolumnę. Dla liczb pierwszych reszta zawsze wynosi p − 1: dla 5 to 4, dla 7 to 6, dla 11 to 10. Dla liczb złożonych — nie (dla wszystkich złożonych większych od 4 wychodzi 0).
To twierdzenie Wilsona: liczba p > 1 jest pierwsza wtedy i tylko wtedy, gdy (p − 1)! daje z dzielenia przez p resztę p − 1. To bardzo wolny sposób sprawdzania pierwszości (dzielenie do pierwiastka z lekcji o pętlach jest dużo szybsze), ale ładnie pokazuje, jak wiele „wie” silnia. Sprawdzisz go w ćwiczeniach.
Najpierw odpowiedz w myślach — wypisz sobie na kartce kolejne wartości zmiennych — a dopiero potem kliknij „Pokaż odpowiedź”.
long long w = 1;
for (int i = 1; i <= 4; i++) w = w * i % 10;
cout << w;
Pokaż odpowiedź
long long w = 1;
for (int i = 1; i <= 12; i++) w = w * i % 10;
cout << w;
Pokaż odpowiedź
long long w = 1;
for (int i = 1; i <= 5; i++) w = w * i % 7;
cout << w;
Pokaż odpowiedź
long long n = 100, m = 97;
if (n >= m) cout << 0;
else cout << "licz";
Pokaż odpowiedź
long long w = 1;
for (int i = 1; i <= 4; i++) w = w * i % 8;
cout << w;
Pokaż odpowiedź
long long s = 1, suma = 0;
for (int i = 1; i <= 5; i++) {
s = s * i % 100;
suma = (suma + s) % 100;
}
cout << suma;
Pokaż odpowiedź
long long w = 1;
for (int i = 1; i <= 10; i++) w = w * i % 11;
cout << w;
Pokaż odpowiedź
int m = 7;
cout << (720 % m) / (120 % m) << " " << 720 / 120 % m;
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ę.
Zera na końcu i czynniki silni
Popatrz na końcówki silni: 5! = 120, 10! = 3 628 800, 15! = 1 307 674 368 000, 20! = 2 432 902 008 176 640 000. Zer na końcu przybywa — jedno, dwa, trzy, cztery. Ile zer ma na końcu 100!? Albo silnia miliarda? To jedno z najsłynniejszych zadań o silni i ma piękne rozwiązanie: wcale nie trzeba liczyć silni, wystarczy policzyć piątki.
Skąd się biorą zera
Każde zero na końcu liczby oznacza, że liczba dzieli się przez 10. Dwa zera — przez 100 = 10 · 10. Ogólnie: tyle zer, ile razy możemy podzielić liczbę przez 10.
A 10 = 2 · 5. Rozłóżmy 10! na czynniki pierwsze:
10! = 2⁸ · 3⁴ · 5² · 7
Dwójek jest aż osiem, ale piątek tylko dwie. Z każdej pary „dwójka + piątka” powstaje jedna dziesiątka, więc par — i zer na końcu — jest tyle, ile piątek: 2. Zgadza się: 3 628 800.
| liczba | dwójki | piątki |
|---|---|---|
| 2 | 1 | — |
| 4 = 2 · 2 | 2 | — |
| 5 | — | 1 |
| 6 = 2 · 3 | 1 | — |
| 8 = 2 · 2 · 2 | 3 | — |
| 10 = 2 · 5 | 1 | 1 |
| razem w 10! | 8 | 2 |
Poniżej każda liczba od 1 do n ma kropki: niebieskie za dwójki i pomarańczowe za piątki w jej rozkładzie. Przesuwaj suwak i obserwuj, że niebieskich kropek jest zawsze dużo więcej. Zwróć uwagę na 25 — ma dwie piątki.
Liczymy piątki — sposób pierwszy
int n;
cin >> n;
long long zera = 0;
for (int i = 1; i <= n; i++) {
int x = i;
while (x % 5 == 0) { // ile piątek ma i?
zera++;
x /= 5;
}
}
cout << zera << "\n";
Przechodzimy po wszystkich liczbach od 1 do n i dla każdej liczymy, ile razy dzieli się przez 5 — pętlą while z lekcji o pętlach. Suma to liczba piątek w n!, czyli liczba zer na końcu.
Dla n = 25: po jednej piątce dają 5, 10, 15 i 20, a 25 = 5 · 5 daje dwie. Razem 6 — i rzeczywiście 25! = 15 511 210 043 330 985 984 000 000.
Ten sposób jest dobry dla n do kilku milionów. Ale dla n = 10¹⁸ pętla nie zdąży.
Dlaczego dwójek jest więcej?
| n | dwójki w n! | piątki w n! | zera |
|---|---|---|---|
| 10 | 8 | 2 | 2 |
| 25 | 22 | 6 | 6 |
| 100 | 97 | 24 | 24 |
| 1000 | 994 | 249 | 249 |
Co druga liczba jest parzysta, a tylko co piąta dzieli się przez 5. Do tego co czwarta liczba daje drugą dwójkę, co ósma — trzecią… Dwójek jest więc zawsze około czterech razy więcej niż piątek.
Każda piątka znajdzie sobie parę wśród dwójek. Dlatego w silni liczba zer na końcu = liczba piątek. W dowolnym innym iloczynie tak być nie musi — o tym za chwilę.
Szybko: n/5 + n/25 + n/125 + …
Zamiast sprawdzać każdą liczbę osobno, policzmy piątki „hurtem”. Weźmy n = 100:
• co piąta liczba od 1 do 100 dzieli się przez 5 — jest ich 100 / 5 = 20 i każda daje co najmniej jedną piątkę,
• co dwudziesta piąta dzieli się przez 25 = 5 · 5 — jest ich 100 / 25 = 4 (25, 50, 75, 100) i każda daje jeszcze jedną, drugą piątkę,
• przez 125 nie dzieli się żadna — 100 / 125 = 0.
Razem 20 + 4 = 24 piątki — tyle samo, co wyliczył wolny program. Ogólnie liczba zer na końcu n! to n / 5 + n / 25 + n / 125 + … (dzielenie całkowite), aż kolejna potęga piątki przekroczy n.
long long n;
cin >> n;
long long zera = 0;
while (n > 0) {
n /= 5; // n/5, potem n/25, n/125…
zera += n;
}
cout << zera << "\n";
Ten zapis jest sprytny: zamiast liczyć potęgi piątki (które przy n = 10¹⁸ mogłyby wyjść poza zakres), dzielimy samo n. Po pierwszym dzieleniu n to 100 / 5 = 20, po drugim 20 / 5 = 4, czyli 100 / 25, po trzecim 4 / 5 = 0, czyli 100 / 125. Dodajemy kolejne wyniki: 20 + 4 + 0.
Dla n = 10¹⁸ pętla robi tylko 26 obrotów — a sama silnia 10¹⁸ ma około 1,8 · 10¹⁹ cyfr. Gdyby wypisywać je po jednej na sekundę, zajęłoby to ponad pół biliona lat.
Dowolna liczba pierwsza: wzór Legendre’a
long long n = 10, p = 3;
long long e = 0, m = n;
while (m > 0) {
m /= p;
e += m;
}
cout << "trojek w " << n << "!: " << e << "\n";
n = 100; p = 7; e = 0; m = n;
while (m > 0) {
m /= p;
e += m;
}
cout << "siodemek w " << n << "!: " << e << "\n";
Piątka niczym się nie wyróżnia — tak samo policzysz, ile razy n! dzieli się przez dowolną liczbę pierwszą p: n / p + n / p² + n / p³ + … To wzór Legendre’a.
Trójki w 10!: 10 / 3 = 3 (liczby 3, 6, 9) i 10 / 9 = 1 (liczba 9 daje drugą trójkę) — razem 4. Zgadza się z rozkładem 10! = 2⁸ · 3⁴ · 5² · 7.
Uwaga: wzór działa tylko dla liczb pierwszych. Ile razy 10! dzieli się przez 4? Nie 10 / 4 + 10 / 16 = 2, tylko 4 razy (bo 2⁸ = 4⁴) — z liczbą złożoną trzeba najpierw rozłożyć ją na czynniki.
Zera na końcu dowolnego iloczynu
int n;
cin >> n;
long long dwojki = 0, piatki = 0;
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
while (x % 2 == 0) { dwojki++; x /= 2; }
while (x % 5 == 0) { piatki++; x /= 5; }
}
cout << min(dwojki, piatki) << "\n";
Gdy mnożymy dowolne liczby, a nie kolejne od 1 do n, dwójek wcale nie musi być więcej. 4 · 25 · 3 = 300: dwie dwójki i dwie piątki, więc dwa zera. 16 · 5 = 80: cztery dwójki, ale tylko jedna piątka — jedno zero.
Ogólnie zer jest tyle, ile pełnych par 2 · 5, czyli min(dwojki, piatki) — funkcja min z lekcji o max i min. W silni ten minimum to zawsze piątki.
Zera rosną skokami
| n | 20 | 21–23 | 24 | 25 | 26–29 | 30 |
|---|---|---|---|---|---|---|
| zera w n! | 4 | 4 | 4 | 6 | 6 | 7 |
Liczba zer zmienia się tylko przy wielokrotnościach 5, bo tylko one dokładają piątki. Przy 25 = 5 · 5 przybywają od razu dwa zera: z 4 skacze na 6. Dlatego żadna silnia nie kończy się dokładnie pięcioma zerami!
Przy 125 = 5³ przybywają trzy zera naraz, przy 625 — cztery. Pamiętaj o tym, gdy zadanie pyta o silnię z dokładnie k zerami — odpowiedź może brzmieć „nie ma takiej”.
Najpierw odpowiedz w myślach — wypisz sobie na kartce kolejne wartości zmiennych — a dopiero potem kliknij „Pokaż odpowiedź”.
long long n = 50, zera = 0;
while (n > 0) {
n /= 5;
zera += n;
}
cout << zera;
Pokaż odpowiedź
int x = 250, ile = 0;
while (x % 5 == 0) {
ile++;
x /= 5;
}
cout << ile;
Pokaż odpowiedź
long long n = 24, zera = 0;
while (n > 0) {
n /= 5;
zera += n;
}
cout << zera;
Pokaż odpowiedź
long long n = 10, e = 0;
while (n > 0) {
n /= 2;
e += n;
}
cout << e;
Pokaż odpowiedź
long long n = 125, zera = 0;
while (n > 0) {
n /= 5;
zera += n;
}
cout << zera;
Pokaż odpowiedź
long long x = 8LL * 125 * 7;
int zera = 0;
while (x % 10 == 0) {
zera++;
x /= 10;
}
cout << zera;
Pokaż odpowiedź
long long n = 7, p = 7, e = 0;
while (n > 0) {
n /= p;
e += n;
}
cout << e;
Pokaż odpowiedź
bool jest = false;
for (int n = 1; n <= 30; n++) {
int m = n, zera = 0;
while (m > 0) {
m /= 5;
zera += m;
}
if (zera == 5) jest = true;
}
cout << (jest ? "tak" : "nie");
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ę.
Silnie olbrzymy — cyfra po cyfrze i log10
Co zrobić, gdy zadanie każe wypisać 100! — wszystkie 158 cyfr? Żaden typ tego nie pomieści, ale Ty potrafisz pomnożyć dowolnie długą liczbę na kartce, cyfra po cyfrze. Komputer też potrafi — jeśli trzymasz cyfry w vectorze. Tak policzysz silnię nawet z tysiąca. W drugiej połowie tej części poznasz nową funkcję, log10, która powie Ci, ile cyfr ma silnia miliona i od jakiej cyfry się zaczyna — choć samej silni nie policzy nikt.
Liczba w vectorze — od końca
W lekcji o napisach dodawałeś olbrzymy zapisane jako napisy. Do mnożenia wygodniej trzymać cyfry w vector<int> — i to od końca: na pozycji 0 cyfra jedności, na pozycji 1 cyfra dziesiątek, na pozycji 2 setek… Liczba 3 628 800 (czyli 10!) wygląda wtedy tak:
Dlaczego od końca? Bo przy mnożeniu liczba rośnie z przodu: 720 · 7 = 5040 ma o jedną cyfrę więcej, a nowa cyfra (5) pojawia się na początku liczby. W odwróconym vectorze „początek liczby” to koniec vectora — nową cyfrę dokładamy zwykłym push_back. Gdybyśmy trzymali cyfry normalnie, trzeba by przesuwać cały vector, żeby zrobić miejsce na początku.
Mnożenie pisemne — tak jak na kartce
| krok | cyfra · 7 + przeniesienie | nowa cyfra | przeniesienie |
|---|---|---|---|
| c[0] | 0 · 7 + 0 = 0 | 0 | 0 |
| c[1] | 2 · 7 + 0 = 14 | 4 | 1 |
| c[2] | 7 · 7 + 1 = 50 | 0 | 5 |
| koniec | zostało 5 | 5 | 0 |
Policzmy 7! z 6! = 720, czyli 720 · 7. Na kartce mnożysz od prawej: każdą cyfrę razy 7, do tego dodajesz to, co „przeszło” z poprzedniej kolumny. Z wyniku zostawiasz ostatnią cyfrę (% 10), a resztę przenosisz dalej (/ 10).
Po ostatniej cyfrze zostało przeniesienie 5 — to nowa cyfra z przodu liczby. Wynik: 5040. Gdy przeniesienie jest większe niż 9 (przy mnożeniu przez liczby kilkucyfrowe), dokładamy kilka cyfr, każdą przez % 10 i / 10.
Zobacz to samo w animacji. Krok mnoży jedną cyfrę, Całe mnożenie kończy bieżące mnożenie, a Następna silnia mnoży wynik przez kolejną liczbę — tak, jak robi to pętla licząca silnię.
vector<int> c = {0, 2, 7}; // 720, od końca
int k = 7;
int p = 0; // przeniesienie
for (int j = 0; j < (int)c.size(); j++) {
int x = c[j] * k + p;
c[j] = x % 10; // zostaje ostatnia cyfra
p = x / 10; // reszta idzie dalej
}
while (p > 0) { // nowe cyfry z przodu liczby
c.push_back(p % 10);
p /= 10;
}
for (int j = (int)c.size() - 1; j >= 0; j--) cout << c[j];
cout << "\n";
To całe mnożenie olbrzyma przez zwykłą liczbę. Pętla idzie po cyfrach od jedności, a zmienna p pamięta przeniesienie między kolumnami.
Po pętli przeniesienie może jeszcze zostać — wtedy dokładamy cyfry na koniec vectora, czyli na początek liczby. while zamiast if, bo przy mnożeniu przez 13 czy 100 przeniesienie bywa dwucyfrowe albo trzycyfrowe.
Na końcu wypisujemy vector od tyłu, żeby liczba wyglądała normalnie.
Cała silnia — dokładnie
int n;
cin >> n;
vector<int> c = {1}; // 0! = 1
for (int i = 2; i <= n; i++) { // mnożymy przez 2, 3, …, n
int p = 0;
for (int j = 0; j < (int)c.size(); j++) {
int x = c[j] * i + p;
c[j] = x % 10;
p = x / 10;
}
while (p > 0) {
c.push_back(p % 10);
p /= 10;
}
}
for (int j = (int)c.size() - 1; j >= 0; j--) cout << c[j];
cout << "\n";
Silnia to tylko wiele mnożeń po kolei, więc wystarczy owinąć mnożenie olbrzyma pętlą po i — dokładnie jak w zwykłej silni, tylko „w” jest teraz vectorem cyfr. Startujemy od {1}, czyli od 1 = 0!.
25! ma 26 cyfr, 50! — 65, a 1000! — 2568. Dla n = 1000 program wykona nieco ponad milion mnożeń cyfr: dla komputera to chwila.
Zmienna x mieści się w int: cyfra (najwyżej 9) razy i (najwyżej kilka tysięcy) plus przeniesienie to ledwie kilkadziesiąt tysięcy.
Co można policzyć z olbrzyma
vector<int> c = {1};
for (int i = 2; i <= 100; i++) {
int p = 0;
for (int j = 0; j < (int)c.size(); j++) {
int x = c[j] * i + p;
c[j] = x % 10;
p = x / 10;
}
while (p > 0) { c.push_back(p % 10); p /= 10; }
}
int suma = 0, zera = 0;
for (int d : c) suma += d;
while (c[zera] == 0) zera++; // zera na końcu liczby
cout << "cyfr: " << c.size() << "\n";
cout << "suma cyfr: " << suma << "\n";
cout << "zera na koncu: " << zera << "\n";
cout << "ostatnia niezerowa: " << c[zera] << "\n";
Gdy olbrzym siedzi w vectorze, łatwo odpowiedzieć na każde pytanie o jego cyfry:
• liczba cyfr to po prostu c.size(),
• sumę cyfr liczysz pętlą „dla każdego”,
• zera na końcu liczby to zera na początku vectora — idziemy od c[0], dopóki są zera,
• pierwsza cyfra po tych zerach to ostatnia niezerowa cyfra liczby.
Zwróć uwagę: 24 zera na końcu 100! — dokładnie tyle, ile wyliczył wzór n / 5 + n / 25 z części 6. Dwa zupełnie różne sposoby, ten sam wynik.
Dodawanie olbrzymów
int n = 25;
vector<int> f = {1}, s = {0}; // bieżąca silnia i suma
for (int i = 1; i <= n; i++) {
int p = 0; // f = f · i
for (int j = 0; j < (int)f.size(); j++) {
int x = f[j] * i + p;
f[j] = x % 10;
p = x / 10;
}
while (p > 0) { f.push_back(p % 10); p /= 10; }
p = 0; // s = s + f
for (int j = 0; j < (int)f.size() || p > 0; j++) {
if (j == (int)s.size()) s.push_back(0);
int x = s[j] + p + (j < (int)f.size() ? f[j] : 0);
s[j] = x % 10;
p = x / 10;
}
}
for (int j = (int)s.size() - 1; j >= 0; j--) cout << s[j];
cout << "\n";
Suma silni 1! + 2! + … + 25! też nie mieści się w long long. Robimy więc to samo co w części 2 — bieżąca silnia i suma — tylko obie są olbrzymami w vectorach.
Dodawanie pisemne znasz z lekcji o napisach: dodajesz cyfry z tej samej kolumny i przeniesienie, zostawiasz % 10, przenosisz / 10. Gdy suma jest krótsza od dodawanej silni, brakujące cyfry dokładamy jako zera (push_back(0)), a cyfry spoza f traktujemy jak 0 — to robi wyrażenie z ? i :.
A silnia miliona? Nowe narzędzie: log10
Silnia miliona ma ponad pięć i pół miliona cyfr. Mnożenie pisemne musiałoby milion razy przejść po coraz dłuższym vectorze — to biliony operacji, zdecydowanie za dużo. Jeśli jednak zadanie pyta tylko o liczbę cyfr albo o pierwsze cyfry, pomoże funkcja log10 z biblioteki cmath.
log10(x) odpowiada na pytanie: do jakiej potęgi trzeba podnieść 10, żeby dostać x? 10² = 100, więc log10(100) = 2. 10³ = 1000, więc log10(1000) = 3. A log10(500)? 500 leży między 100 a 1000, więc wynik jest między 2 a 3 — wychodzi około 2,7.
cout << fixed << setprecision(4);
cout << log10(1) << "\n";
cout << log10(9) << "\n";
cout << log10(10) << "\n";
cout << log10(500) << "\n";
cout << log10(999) << "\n";
cout << log10(1000) << "\n";
cout << log10(3628800) << "\n";
Popatrz na część przed kropką. Liczby jednocyfrowe (1–9) mają logarytm od 0 do 0,99…, dwucyfrowe od 1 do 1,99…, trzycyfrowe (500, 999) od 2 do 2,99…, a 1000 — dokładnie 3, bo ma już cztery cyfry.
Czyli: liczba cyfr x = floor(log10(x)) + 1. Dla 10! = 3 628 800: floor(6,5598) + 1 = 7 cyfr. Zgadza się.
Funkcję floor znasz z lekcji o zaokrąglaniu — zaokrągla w dół.
Logarytm iloczynu to suma logarytmów
Żeby użyć wzoru, trzeba znać log10(n!) — a samej silni miliona nie mamy. Pomaga najważniejsza własność logarytmu: log10(a · b) = log10(a) + log10(b). Sprawdź: 100 · 1000 = 100 000, a log10(100) + log10(1000) = 2 + 3 = 5 = log10(100 000). Mnożenie zamienia się w dodawanie wykładników!
Silnia to iloczyn, więc jej logarytm to suma: log10(n!) = log10(1) + log10(2) + … + log10(n). Każdy składnik jest małą liczbą (log10 miliona to tylko 6), więc suma spokojnie mieści się w double.
double L = 0;
for (int i = 1; i <= 1000000; i++) {
L += log10(i); // L = log10(i!)
if (i == 10 || i == 100 || i == 1000 || i == 1000000) {
cout << i << "! ma " << (long long)floor(L) + 1 << " cyfr\n";
}
}
Milion dodawań to ułamek sekundy. Dla 100! i 1000! wyniki zgadzają się z tym, co policzyło mnożenie pisemne (158 i 2568 cyfr) — a dla miliona dostajemy odpowiedź, której mnożeniem nie dałoby się policzyć.
Dla n = 0 i n = 1 suma to 0 (log10(1) = 0), więc wynik to 1 cyfra — zgadza się, 0! = 1! = 1.
Pierwsza cyfra: część ułamkowa logarytmu
double L = 0;
for (int i = 1; i <= 1000000; i++) {
L += log10(i);
if (i == 10 || i == 100 || i == 1000 || i == 1000000) {
double f = L - floor(L); // część ułamkowa
cout << i << "!: " << (int)pow(10, f)
<< ", trzy cyfry: " << (int)pow(10, f + 2) << "\n";
}
}
Część całkowita logarytmu mówi, ile cyfr ma liczba. Część ułamkowa f mówi, jak się zaczyna. Dla 10!: L = 6,5598, czyli 10! = 10⁶ · 10^0,5598 = 10⁶ · 3,6288.
10^f to zawsze liczba od 1 do 10 — jej część całkowita to pierwsza cyfra. Potęgę liczy funkcja pow(a, b), czyli a do potęgi b (wynik to double). Trzy pierwsze cyfry to część całkowita z 10^f · 100 = 10^(f + 2).
double pamięta około 15–16 cyfr, a suma miliona logarytmów może pomylić się na ostatnich miejscach po przecinku. Do liczby cyfr i kilku pierwszych cyfr to wystarczy z ogromnym zapasem. Ale ostatnich cyfr silni logarytmem nie policzysz — od tego są modulo (część 5), liczenie piątek (część 6) i mnożenie pisemne. A gdy n ≤ 20, policz silnię dokładnie w long long — po co ryzykować.
Najpierw odpowiedz w myślach — wypisz sobie na kartce kolejne wartości zmiennych — a dopiero potem kliknij „Pokaż odpowiedź”.
vector<int> c = {4, 2, 0, 1};
for (int j = (int)c.size() - 1; j >= 0; j--) cout << c[j];
Pokaż odpowiedź
vector<int> c = {5, 2}; // 25
int p = 0;
for (int j = 0; j < 2; j++) {
int x = c[j] * 4 + p;
c[j] = x % 10;
p = x / 10;
}
cout << p << " " << c[1] << c[0];
Pokaż odpowiedź
int x = 9 * 13 + 4;
cout << x % 10 << " " << x / 10;
Pokaż odpowiedź
cout << (long long)floor(log10(99999)) + 1;
Pokaż odpowiedź
cout << log10(100) + log10(1000);
Pokaż odpowiedź
double L = 0;
for (int i = 1; i <= 5; i++) L += log10(i);
cout << (long long)floor(L) + 1;
Pokaż odpowiedź
double L = log10(3628800);
double f = L - floor(L);
cout << (int)pow(10, f + 1);
Pokaż odpowiedź
vector<int> c = {0, 0, 0, 2, 7}; // 72000
int zera = 0;
while (c[zera] == 0) zera++;
cout << zera << " " << c[zera];
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ę.
Liczenie sposobów — podium, wybieranie i trójkąt Pascala
Silnia odpowiada na pytanie „na ile sposobów można ustawić wszystkie rzeczy w rzędzie”. Ale zadania pytają też o inne rzeczy: ile może być podiów w biegu, ile drużyn da się wybrać z klasy, ile słów da się ułożyć z liter, w których coś się powtarza. Wszystkie te odpowiedzi zbudujemy z silni i z drzewka wyborów z części 1. Ta gałąź matematyki nazywa się kombinatoryką — a zadania z niej pojawiają się na olimpiadzie bardzo często.
Podium — nie wszyscy stają na pudle
int n = 8, k = 3; // 8 biegaczy, 3 medale
long long w = 1;
for (int i = n; i > n - k; i--) {
w *= i; // 8 · 7 · 6
}
cout << w << "\n";
W biegu startuje 8 zawodników. Na ile sposobów może wyglądać podium? Drzewko wyborów: złoto może zdobyć każdy z 8, srebro — każdy z 7 pozostałych, brąz — każdy z 6 pozostałych. Razem 8 · 7 · 6 = 336.
To silnia, która zatrzymała się w połowie: zamiast 8 · 7 · 6 · 5 · 4 · 3 · 2 · 1 mamy tylko trzy pierwsze czynniki. Inaczej: 8! / 5! — wszystkie czynniki od 1 do 5 się skracają (część 4).
Ogólnie: k miejsc z kolejnością spośród n osób to n · (n − 1) · … · (n − k + 1) = n! / (n − k)! — k czynników, od n w dół.
Kody: z powtórzeniami i bez
int k = 3; // kod z trzech cyfr
long long wszystkie = 1, rozne = 1;
for (int i = 0; i < k; i++) {
wszystkie *= 10; // 10 · 10 · 10
rozne *= 10 - i; // 10 · 9 · 8
}
cout << wszystkie << " " << rozne << "\n";
Kod do zamka ma 3 cyfry. Jeśli cyfry mogą się powtarzać, na każdej pozycji jest 10 możliwości: 10 · 10 · 10 = 1000 kodów (od 000 do 999 — zgadza się).
Jeśli cyfry muszą być różne, to jak przy podium: 10 możliwości na pierwszej pozycji, 9 na drugiej, 8 na trzeciej — 720 kodów.
Różnica między tymi dwoma wynikami to kody, w których coś się powtarza (na przykład 112 albo 777) — jest ich 280.
Wybieranie bez kolejności
Czworo przyjaciół — A, B, C, D — wita się i każdy podaje rękę każdemu. Ile jest uścisków? Licząc „z kolejnością”, pierwszą osobę wybierasz na 4 sposoby, drugą na 3: 4 · 3 = 12. Ale uścisk A z B to ten sam uścisk co B z A — każdą parę policzyliśmy dwa razy. Uścisków jest więc 12 / 2 = 6: AB, AC, AD, BC, BD, CD.
To samo z większymi grupami. Z 5 osób wybieramy 3-osobową komisję, w której wszyscy mają równe prawa. Z kolejnością: 5 · 4 · 3 = 60. Ale ta sama trójka, na przykład A, B, C, pojawia się w tych 60 wynikach na tyle sposobów, na ile można ją ustawić: 3! = 6 razy (ABC, ACB, BAC, BCA, CAB, CBA). Komisji jest więc 60 / 6 = 10.
C(n, k) = n! / (k! · (n − k)!) — czytamy „n nad k”. Skąd ten wzór? n! / (n − k)! to wybieranie z kolejnością (jak podium), a dzielimy przez k!, bo każda grupa była policzona k! razy. Przykłady: uściski dłoni to C(n, 2) = n · (n − 1) / 2, a komisja 3 z 5 to C(5, 3) = 10.
Liczymy C(n, k) bez przepełnienia
Wzór z silniami jest piękny, ale w programie się nie sprawdza: żeby policzyć C(30, 3) = 4060, musiałbyś najpierw policzyć 30!, a to już się nie mieści. Lepiej liczyć krok po kroku, na zmianę mnożąc i dzieląc:
c = 1, a potem dla i = 1, 2, …, k: c = c · (n − k + i) / i
Po każdym kroku c jest liczbą całkowitą — to C(n − k + i, i) — więc dzielenie nigdy nie gubi reszty. Liczby w środku są niewiele większe od wyniku.
long long n = 10, k = 3;
long long c = 1;
for (long long i = 1; i <= k; i++) {
c = c * (n - k + i) / i; // najpierw mnożymy, potem dzielimy
cout << "i = " << i << ": c = " << c << "\n";
}
| i | c · (n − k + i) | / i | to jest |
|---|---|---|---|
| 1 | 1 · 8 = 8 | 8 | C(8, 1) |
| 2 | 8 · 9 = 72 | 36 | C(9, 2) |
| 3 | 36 · 10 = 360 | 120 | C(10, 3) |
long long n = 10, k = 3;
long long c = 1;
for (long long i = 1; i <= k; i++) {
c *= (n - k + i) / i; // BŁĄD: najpierw dzielenie
}
cout << c << "\n";
Kolejność jest ważna! Zapis c *= (n - k + i) / i najpierw dzieli, a dopiero potem mnoży. Dla i = 2 liczy 9 / 2 = 4 (dzielenie całkowite gubi połówkę) i wynik się psuje: 96 zamiast 120.
Dzielenie jest bezpieczne tylko wtedy, gdy dzielimy cały iloczyn c * (n - k + i) — on zawsze dzieli się przez i bez reszty.
Przydatna sztuczka: C(n, k) = C(n, n − k) (wybrać 3 osoby do komisji to to samo, co wybrać 2, które w niej nie będą). Gdy k jest duże, weź k = min(k, n - k) — pętla będzie krótsza.
long long n = 49, k = 6, c = 1;
for (long long i = 1; i <= k; i++) c = c * (n - k + i) / i;
cout << "Lotto: " << c << "\n";
n = 60; k = 30; c = 1;
for (long long i = 1; i <= k; i++) c = c * (n - k + i) / i;
cout << "C(60, 30) = " << c << "\n";
W Lotto losuje się 6 liczb z 49. Wszystkich możliwych zakładów jest C(49, 6) = 13 983 816 — szansa na szóstkę z jednym kuponem to mniej niż jeden do trzynastu milionów.
C(60, 30) ≈ 1,2 · 10¹⁷ wciąż mieści się w long long, a liczby w środku pętli nie przekraczają kilku trylionów. Dla większych n trzeba już liczyć modulo — tym zajmie się trójkąt Pascala.
Trójkąt Pascala
Ułóżmy wartości C(n, k) w trójkąt: w wierszu numer n (licząc od 0) stoją C(n, 0), C(n, 1), …, C(n, n). Na brzegach są same jedynki (zero osób albo wszystkie osoby da się wybrać tylko na jeden sposób), a w środku każda liczba jest sumą dwóch liczb nad nią:
Dlaczego C(5, 2) = C(4, 1) + C(4, 2), czyli 10 = 4 + 6? Wybieramy 2 osoby z 5, wśród których jest Ala. Są dwie możliwości:
• Ala jest w grupie — wtedy z pozostałych 4 osób dobieramy jeszcze 1: C(4, 1) = 4 sposoby,
• Ali nie ma w grupie — wtedy obie osoby wybieramy z pozostałych 4: C(4, 2) = 6 sposobów.
Przypadki się nie nakładają, więc je dodajemy (pamiętasz ramkę „mnożyć czy dodawać?”): 4 + 6 = 10.
int t[7][7];
for (int n = 0; n < 7; n++) {
t[n][0] = t[n][n] = 1; // brzegi
for (int k = 1; k < n; k++) {
t[n][k] = t[n - 1][k - 1] + t[n - 1][k];
}
for (int k = 0; k <= n; k++) cout << t[n][k] << " ";
cout << "\n";
}
Trójkąt liczy symbole Newtona samym dodawaniem — bez mnożenia i, co najważniejsze, bez dzielenia. A dodawanie można robić modulo! Gdy zadanie każe wypisać C(2000, 1000) mod 10⁹ + 7 (ta liczba ma ponad 600 cyfr), liczysz tablicę 2001 × 2001 z t[n][k] = (t[n - 1][k - 1] + t[n - 1][k]) % MOD. Wzoru z silniami użyć się nie da, bo reszt nie wolno dzielić (część 5).
Anagramy: gdy litery się powtarzają
Ile różnych słów da się ułożyć z liter słowa mama? Gdyby wszystkie litery były różne — na przykład m₁, a₁, m₂, a₂ — ustawień byłoby 4! = 24. Ale zamiana miejscami m₁ i m₂ daje to samo słowo, podobnie zamiana a₁ i a₂.
Każde słowo policzyliśmy więc 2! · 2! = 4 razy (dwa układy liter m razy dwa układy liter a). Różnych słów jest 24 / 4 = 6: aamm, amam, amma, maam, mama, mmaa.
Ogólnie: słowo z n liter, w którym jedna litera występuje a razy, druga b razy, …, ma n! / (a! · b! · …) różnych ustawień.
string s;
cin >> s;
long long f[21];
f[0] = 1;
for (int i = 1; i <= 20; i++) f[i] = f[i - 1] * i;
int ile[26] = {0}; // licznik każdej litery
for (char c : s) ile[c - 'a']++;
long long w = f[s.size()];
for (int i = 0; i < 26; i++) w /= f[ile[i]];
cout << w << "\n";
Liczniki liter znasz z lekcji o napisach. Litery, których w słowie nie ma, mają licznik 0, a 0! = 1 — dzielenie przez 1 niczego nie psuje. Tu po raz kolejny przydaje się umowa 0! = 1. Dla mississippi: 11! / (1! · 4! · 4! · 2!) = 39 916 800 / 1152 = 34 650.
Trasy na kratce
Idziesz z lewego dolnego rogu kratki do prawego górnego, robiąc kroki o jedną kratkę w prawo (P) albo w górę (G). Ile jest takich tras na kratce 3 × 2?
Każda trasa to słowo z trzech liter P i dwóch liter G — narysowana trasa to PPGPG. A różnych słów z liter PPPGG jest, jak przed chwilą, 5! / (3! · 2!) = 10. To samo co C(5, 2): z 5 kroków wybieramy, które 2 idą w górę.
Ogólnie na kratce a × b jest C(a + b, a) tras. W ćwiczeniach policzysz też trasy, które muszą przejść przez wybrany punkt — wtedy trasę dzielisz na dwa kawałki i mnożysz.
n!. Wybrane k z n, kolejność się liczy (podium, kody bez powtórzeń): n · (n − 1) · … · (n − k + 1). Z powtórzeniami (kody, hasła): n · n · … · n. Wybrane k z n bez kolejności (drużyny, uściski, Lotto): C(n, k). Ustawienia z powtórzonymi elementami (anagramy): n! / (a! · b! · …). Trasy na kratce a × b: C(a + b, a).
Najpierw odpowiedz w myślach — wypisz sobie na kartce kolejne wartości zmiennych — a dopiero potem kliknij „Pokaż odpowiedź”.
long long w = 1;
for (int i = 5; i > 3; i--) w *= i;
cout << w;
Pokaż odpowiedź
long long n = 10;
cout << n * (n - 1) / 2;
Pokaż odpowiedź
long long n = 6, k = 2, c = 1;
for (long long i = 1; i <= k; i++) c = c * (n - k + i) / i;
cout << c;
Pokaż odpowiedź
long long n = 7, k = 7, c = 1;
for (long long i = 1; i <= k; i++) c = c * (n - k + i) / i;
cout << c;
Pokaż odpowiedź
int t[5][5];
for (int n = 0; n < 5; n++) {
t[n][0] = t[n][n] = 1;
for (int k = 1; k < n; k++) t[n][k] = t[n - 1][k - 1] + t[n - 1][k];
}
cout << t[4][2];
Pokaż odpowiedź
cout << 24 / (2 * 2);
Pokaż odpowiedź
long long a = 2, b = 2, c = 1;
for (long long i = 1; i <= a; i++) c = c * (b + i) / i;
cout << c;
Pokaż odpowiedź
long long w = 1;
for (int i = 0; i < 4; i++) w *= 10 - i;
cout << w;
Pokaż odpowiedź
long long c = 1;
for (long long i = 1; i <= 3; i++) c *= (6 - 3 + i) / i;
cout << c;
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ę.
Baza zadań: silnia w praktyce
Znasz już wszystkie narzędzia: ustawienia w kolejce i drzewko wyborów, pętlę liczącą silnię i jej pułapki, granice typów i sprawdzanie przed mnożeniem, tablicę silni i dzielenie silni, silnię modulo, liczenie piątek i wzór Legendre’a, mnożenie pisemne w vectorze, logarytmy oraz liczenie sposobów z symbolem Newtona i trójkątem Pascala. Czas na zadania, które łączą kilka z tych rzeczy naraz. Są ułożone od najłatwiejszego do najtrudniejszego: najpierw rozgrzewka z jednym, dwoma pomysłami, potem zadania średnie, a na końcu trudne — z wielkim finałem.
Przy każdym zadaniu widać, jakich zagadnień używa — także tych z poprzednich lekcji, jak sito Eratostenesa, liczniki liter czy dzielenie z resztą. Jeśli coś brzmi obco, wróć do odpowiedniej części — mapa lekcji jest na górze strony. A tu masz najważniejsze schematy z lekcji w jednym miejscu:
Ściąga: gotowe schematy
Silnia w pętli
long long w = 1;
for (int i = 1; i <= n; i++)
w *= i;
Start od 1, warunek <=. Działa dla n = 0. Liczby ujemne wyłap if-em.
Granice typów
int do 12!
long long do 20!
if (w > x / i) // w·i > x
break;
Powyżej 20! — tylko modulo, piątki, cyfry w vectorze albo log10.
Tablica silni
long long f[21];
f[0] = 1;
for (int i = 1; i <= 20; i++)
f[i] = f[i - 1] * i;
n! / k! to iloczyn od k + 1 do n. Silnie cyfr: tablica f[0..9].
Silnia modulo
const long long MOD = 1e9 + 7; w = w * i % MOD; if (n >= m) // n! % m == 0
Reszta po każdym kroku, w w long long. Reszt nie dzielimy.
Zera i czynniki
long long z = 0;
while (n > 0) {
n /= 5; // albo /= p
z += n;
}
Zera n! = piątki. Dowolny iloczyn: min(dwójki, piątki).
Olbrzym w vectorze
vector<int> c = {1}; // od końca
x = c[j] * i + p;
c[j] = x % 10; p = x / 10;
// po pętli, dopóki p > 0:
c.push_back(p % 10); p /= 10;
Wypisuj od tyłu. 1000! ma 2568 cyfr.
Logarytmy
double L = 0;
for (int i = 1; i <= n; i++)
L += log10(i);
cyfry = floor(L) + 1;
pierwsza = (int)pow(10, L - floor(L));
Tylko liczba cyfr i pierwsze cyfry — nigdy ostatnie.
Liczenie sposobów
n! // wszystkie w rzędzie n·(n-1)·…·(n-k+1) // podium c = c * (n-k+i) / i // C(n, k) t[n][k] = t[n-1][k-1] + t[n-1][k];
Anagramy: n! / (a! · b! · …). Trasy: C(a + b, a).
long long; jeśli n jest większe, zadanie na pewno pyta o coś innego. 2) Rozpoznaj, o co pyta: reszta z dzielenia → modulo po każdym kroku; zera na końcu albo „ile razy dzieli się przez p” → piątki i wzór Legendre’a; wszystkie cyfry → vector cyfr; liczba cyfr albo pierwsze cyfry → log10. 3) Przy liczeniu sposobów narysuj drzewko wyborów: czy kolejność się liczy? czy coś się powtarza? 4) Sprawdzaj przed mnożeniem, czy nie przekroczysz typu. 5) Przetestuj skrajności: n = 0 (0! = 1!), n = 1, liczby ujemne, n = 20 i n = 21.
Rozgrzewka · zadania 1–10
Jeden, dwa pomysły naraz: turniej każdy z każdym, pary na balu, matematyka przed fizyką, dyżurni, seria na półce, silnie w przedziale, ostatnia cyfra sumy, dzielenie silni, silnia z odstępami i 10! sekund.
Średnie · zadania 11–20
Kilka pomysłów naraz: zera iloczynu silni, pary na wycieczkę, samorząd klasowy, lotto, droga do szkoły, mikołajki, rozkład silni na czynniki, numer ustawienia, iloczyn silni modulo i silnia z d cyframi.
Trudne · zadania 21–28
Ostatnia niezerowa cyfra, zera w innym systemie, najmniejsza silnia podzielna przez k, dzielniki silni, numer anagramu, cukierki dla dzieci, pierwsze cyfry olbrzyma — a na koniec wielki finał: kalkulator silni.