C++ · Etap 2 · Lekcja 15

Silnia — od kolejki po lody do liczb olbrzymów

Na ile sposobów pięć osób może stanąć w kolejce? Ile zer ma na końcu liczba 100!? Ile cyfr ma silnia miliona i ile jest możliwych zakładów w Lotto? Wszystkie te pytania kręcą się wokół jednego, bardzo prostego pomysłu: pomnóż wszystkie liczby od 1 do n. W tej lekcji zobaczysz, skąd się bierze silnia, policzysz ją pętlą krok po kroku, przekonasz się, jak szybko rozsadza typy int i long long, a potem poznasz sposoby, żeby mimo to odpowiadać na pytania o naprawdę wielkie silnie: modulo, liczenie piątek, mnożenie pisemne i logarytmy. Na koniec użyjesz silni do liczenia sposobów — od podium po trójkąt Pascala. Po każdej części czekają ćwiczenia ze sprawdzarką.

64 ćwiczenia w trakcie lekcji28 zadań w bazie na koniec92 ze sprawdzarką C++

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.

CZĘŚĆ 01–03

Silnia i pętla

Ustawienia w kolejce, n! i 0! = 1, pętla krok po kroku i granice typów int i long long.

CZĘŚĆ 04–05

Tablica i modulo

Wszystkie silnie w tablicy, dzielenie silni, silnie cyfr, reszta z dzielenia silni i słynne 10⁹ + 7.

CZĘŚĆ 06–07

Zera i olbrzymy

Ile zer ma silnia na końcu, czynniki pierwsze silni, mnożenie pisemne w vectorze i liczba cyfr przez log10.

CZĘŚĆ 08

Liczenie sposobów

Podium, kody, uściski dłoni, symbol Newtona, trójkąt Pascala, anagramy i trasy na kratce.

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. W tej lekcji uważaj szczególnie na typ wyniku: silnia bardzo szybko przestaje mieścić się w 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ą.

nr1. miejsce2. miejsce3. miejsce
1ABC
2ACB
3BAC
4BCA
5CAB
6CBA

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.

Ustawiarka — wszystkie kolejki
Ustawiarka działa po włączeniu JavaScriptu. Dla trzech osób A, B, C: ABC, ACB, BAC, BCA, CAB, CBA — 6 ustawień.

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.

startBCCBAACCABABBACABCACBBACBCACABCBA1. miejsce: 3 możliwości2. miejsce: 2 możliwości3. miejsce: 1 możliwość3 · 2 · 1 = 6 ustawień
Każda ścieżka od startu w dół to jedno ustawienie kolejki. Z każdego węzła wychodzi o jedną gałąź mniej niż z poprzedniego poziomu: 3, potem 2, potem 1.

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.

nn! jako iloczynn!
111
21 · 22
31 · 2 · 36
41 · 2 · 3 · 424
51 · 2 · 3 · 4 · 5120
61 · 2 · … · 6720
71 · 2 · … · 75 040
81 · 2 · … · 840 320
91 · 2 · … · 9362 880
101 · 2 · … · 103 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.

Silnia 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

wykrzyknik.cpp
cout << !5 << "\n";
cout << !0 << "\n";
cout << !1 + !1 << "\n";
▶ Wyjście
0 1 0

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:

kolejne.cpp
int w = 1;
for (int n = 1; n <= 8; n++) {
    w = w * n;   // z (n-1)! robimy n!
    cout << n << "! = " << w << "\n";
}
▶ Wyjście
1! = 1 2! = 2 3! = 6 4! = 24 5! = 120 6! = 720 7! = 5040 8! = 40320

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?

silniaz następnejwynik
4!—24
3!4! / 4 = 24 / 46
2!3! / 3 = 6 / 32
1!2! / 2 = 2 / 21
0!1! / 1 = 1 / 11

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ą

silnia.cpp
#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;
}
▶ Wejście 1
4
▶ Wyjście 1
4! = 24
▶ Wejście 2
0
▶ Wyjście 2
0! = 1

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.

obok_siebie.cpp
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
▶ Wyjście
12

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.

Mnożyć czy dodawać? Gdy wybór składa się z kilku etapów po kolei (najpierw pierwsze miejsce, potem drugie; najpierw górna półka, potem dolna) i każdy wybór na jednym etapie pasuje do każdego wyboru na następnym — liczby możliwości mnożymy. Gdy masz kilka osobnych przypadków, które się nie nakładają (na przykład: pierwsza stoi Ala albo pierwszy stoi Bartek) — dodajemy.
Sprawdź się w głowie

Najpierw policz w głowie — wypisz sobie na kartce kolejne iloczyny — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
int w = 1;
for (int i = 1; i <= 4; i++) w *= i;
cout << w;
Pokaż odpowiedź
24To 4! = 1 · 2 · 3 · 4.
Co wypisze ten fragment?
int w = 1;
for (int i = 1; i <= 3; i++) w *= i;
cout << w * w;
Pokaż odpowiedź
363! = 6, a 6 · 6 = 36. To liczba ustawień dwóch półek po 3 książki.
Co wypisze ten fragment?
int w = 1;
for (int i = 1; i <= 0; i++) w *= i;
cout << w;
Pokaż odpowiedź
1Warunek 1 <= 0 jest od razu fałszywy, pętla się nie wykona i zostaje 1 — czyli 0! = 1.
Co wypisze ten fragment?
cout << !5 + !0;
Pokaż odpowiedź
1!5 to fałsz (0), !0 to prawda (1): 0 + 1 = 1. Wykrzyknik w C++ to „nie”, a nie silnia!
Co wypisze ten fragment?
int w = 1;
for (int i = 1; i <= 6; i++) w *= i;
cout << w / 120;
Pokaż odpowiedź
66! = 720, a 720 / 120 = 6. Inaczej: 6! / 5! = 6, bo 6! = 5! · 6.
Ilu sposobami 5 rycerzy usiądzie przy okrągłym stole? Co wypisze fragment?
int n = 5, w = 1;
for (int i = 1; i <= n - 1; i++) w *= i;
cout << w;
Pokaż odpowiedź
24Przy okrągłym stole jednego rycerza sadzamy „na stałe”, a pozostali 4 siadają na 4! = 24 sposoby.
Co wypisze ten fragment?
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ź
720Najpierw w = 3! = 6, a potem v = 6! = 720. To (3!)! — silnia z silni.
5 osób, Ala i Bartek chcą stać obok siebie. Co wypisze fragment?
int w = 1;
for (int i = 2; i <= 4; i++) w *= i;
cout << 2 * w;
Pokaż odpowiedź
48Pętla od 2 do 4 liczy 4! = 24 (mnożenie przez 1 można pominąć). Para to jeden element, więc 4 elementy: 4! = 24, razy 2 kierunki pary: 48.
Ć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 →

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.

Pętla liczy silnię — obrót po obrocie

        
iw po w *= i
Animacja działa po włączeniu JavaScriptu.
obrótii <= 5?w przedw po w *= i
11tak11
22tak12
33tak26
44tak624
55tak24120
—6niekoniec 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

start_od_zera.cpp
int n = 5;
long long w = 0;                 // BŁĄD: start od zera
for (int i = 1; i <= n; i++) {
    w *= i;
}
cout << w << "\n";
▶ Wyjście
0

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

o_jeden_za_malo.cpp
int n = 5;
long long w = 1;
for (int i = 1; i < n; i++) {    // BŁĄD: < zamiast <=
    w *= i;
}
cout << w << "\n";
▶ Wyjście
24

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?

od_dwojki.cpp
int n = 5;
long long w = 1;
for (int i = 2; i <= n; i++) {   // mnożenie przez 1 pomijamy
    w *= i;
}
cout << w << "\n";
▶ Wyjście
120

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

ujemne.cpp
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";
}
▶ Wejście 1
-3
▶ Wyjście 1
BRAK
▶ Wejście 2
0
▶ Wyjście 2
1

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

w_dol.cpp
int n = 5;
long long w = 1;
for (int i = n; i >= 1; i--) {
    w *= i;                      // 5 · 4 · 3 · 2 · 1
}
cout << w << "\n";
▶ Wyjście
120
while.cpp
int n = 5;
long long w = 1;
int i = 1;
while (i <= n) {
    w *= i;
    i++;
}
cout << w << "\n";
▶ Wyjście
120

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

bez_resetu.cpp
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";
}
▶ Wejście
3 3 2 4
▶ Wyjście
6 12 288
z_resetem.cpp
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";
}
▶ Wejście
3 3 2 4
▶ Wyjście
6 2 24

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

od_a_do_b.cpp
int a = 5, b = 7;
long long w = 1;
for (int i = a; i <= b; i++) {
    w *= i;                      // 5 · 6 · 7
}
cout << w << "\n";
▶ Wyjście
210

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

podwojna.cpp
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";
▶ Wyjście
105 384

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

suma_wolno.cpp
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";
▶ Wyjście
33
suma_szybko.cpp
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";
▶ Wyjście
33

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.

Sprawdź się w głowie

Najpierw odpowiedz w myślach — wypisz sobie na kartce kolejne wartości zmiennych — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
long long w = 1;
for (int i = 1; i <= 6; i++) w *= i;
cout << w;
Pokaż odpowiedź
7206! = 5! · 6 = 120 · 6 = 720.
Co wypisze ten fragment?
long long w = 1;
for (int i = 1; i < 6; i++) w *= i;
cout << w;
Pokaż odpowiedź
120Warunek i < 6 zatrzymuje pętlę na i = 5 — to 5!, a nie 6!.
Co wypisze ten fragment?
long long w = 1;
for (int i = 3; i <= 5; i++) w *= i;
cout << w;
Pokaż odpowiedź
60Iloczyn od 3 do 5: 3 · 4 · 5 = 60. To 5! / 2! = 120 / 2.
Co wypisze ten fragment?
long long w = 1;
for (int i = 9; i >= 1; i -= 2) w *= i;
cout << w;
Pokaż odpowiedź
9459!! = 9 · 7 · 5 · 3 · 1 = 945.
Co wypisze ten fragment?
long long w = 1;
for (int i = 6; i >= 1; i -= 2) w *= i;
cout << w;
Pokaż odpowiedź
486!! = 6 · 4 · 2 = 48.
Co wypisze ten fragment?
long long s = 1, suma = 0;
for (int i = 1; i <= 3; i++) {
    s *= i;
    suma += s;
}
cout << suma;
Pokaż odpowiedź
91! + 2! + 3! = 1 + 2 + 6 = 9.
Co wypisze ten fragment?
int n = -2;
long long w = 1;
for (int i = 1; i <= n; i++) w *= i;
cout << w;
Pokaż odpowiedź
1Dla ujemnego n pętla się nie wykona i zostaje 1 — to dlatego liczby ujemne trzeba wyłapać ifem przed pętlą.
Ile razy wykona się mnożenie w *= i? Co wypisze fragment?
int ile = 0;
for (int i = 2; i <= 10; i++) ile++;
cout << ile;
Pokaż odpowiedź
9Licznik przyjmuje wartości od 2 do 10 — to 9 obrotów. Pętla od 2 liczy 10! jednym mnożeniem mniej niż pętla od 1.
Co wypisze ten fragment?
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ź
-191 − 2 + 6 − 24 = −19.
Ć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 →

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

nn · n2ⁿn!
1121
3986
52532120
101001 0243 628 800
1522532 768≈ 1,3 · 10¹²
204001 048 576≈ 2,4 · 10¹⁸
522 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.

Gdzie pęka typ? — przesuwaj suwak
n = 13
Suwak działa po włączeniu JavaScriptu.

int pęka po 12!

int_peka.cpp
int w = 1;
for (int i = 1; i <= 17; i++) {
    w *= i;
    if (i >= 11) cout << i << "! = " << w << "\n";
}
▶ Wyjście
11! = 39916800 12! = 479001600 13! = 1932053504 14! = 1278945280 15! = 2004310016 16! = 2004189184 17! = -288522240

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_peka.cpp
long long w = 1;
for (int i = 1; i <= 22; i++) {
    w *= i;
    if (i >= 19) cout << i << "! = " << w << "\n";
}
▶ Wyjście
19! = 121645100408832000 20! = 2432902008176640000 21! = -4249290049419214848 22! = -1250660718674968576

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

Granice silni 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.

najwieksza_silnia.cpp
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";
▶ Wyjście
19! = 121645100408832000

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⁹

czy_wieksza.cpp
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";
▶ Wejście 1
1000000000 1000000000000000000
▶ Wyjście 1
TAK
▶ Wejście 2
5 120
▶ Wyjście 2
NIE

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

czy_silnia.cpp
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";
▶ Wejście 1
5040
▶ Wyjście 1
5040 = 7!
▶ Wejście 2
100
▶ Wyjście 2
NIE

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?

cyfry.cpp
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";
    }
}
▶ Wyjście
5! ma 3 cyfr 10! ma 7 cyfr 15! ma 13 cyfr 20! ma 19 cyfr

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.cpp
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";
    }
}
▶ Wyjście
20! = 2.4329e+18 25! = 1.55112e+25 170! = 7.25742e+306 171! = inf

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

Sprawdź się w głowie

Najpierw odpowiedz w myślach — wypisz sobie na kartce kolejne wartości zmiennych — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
long long w = 1;
for (int i = 1; i <= 12; i++) w *= i;
cout << w / 11 / 12;
Pokaż odpowiedź
362880012! / 11 / 12 = 10! = 3 628 800.
Czy ten program wypisze prawdziwe 13!? Co wypisze?
int w = 1;
for (int i = 1; i <= 13; i++) w *= i;
cout << (w > 479001600 ? "wieksze" : "mniejsze");
Pokaż odpowiedź
wiekszeUwaga, pułapka: przepełniony wynik 1 932 053 504 jest akurat większy od 12!, więc porównanie „wygląda dobrze” — ale to wciąż nie jest 13! (6 227 020 800). Po przepełnieniu porównania nic nie gwarantują.
Co wypisze ten fragment?
long long x = 1000;
long long w = 1;
int n = 1;
while (w <= x / (n + 1)) {
    n++;
    w *= n;
}
cout << n;
Pokaż odpowiedź
66! = 720 ≤ 1000, a 7! = 5040 > 1000. Największa silnia nie większa niż 1000 to 6!.
Co wypisze ten fragment?
long long x = 24, w = 1;
int n = 0;
while (w < x) {
    n++;
    w *= n;
}
cout << n << " " << (w == x);
Pokaż odpowiedź
4 1Kolejne silnie: 1, 1, 2, 6, 24. Pętla zatrzymuje się na 4! = 24 i trafiła dokładnie — porównanie daje 1.
Co wypisze ten fragment?
long long w = 1;
for (int i = 1; i <= 10; i++) w *= i;
cout << to_string(w).size();
Pokaż odpowiedź
710! = 3 628 800 ma 7 cyfr.
Ile obrotów wykona pętla (ile razy wykona się w *= i)? Co wypisze fragment?
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ź
3Mnożymy przez 2, 3 i 4 (w = 24). Przy i = 5: 24 > 100 / 5 = 20 — następna silnia przekroczyłaby 100, więc break. Trzy mnożenia zamiast miliarda.
Co wypisze ten fragment?
double w = 1;
for (int i = 1; i <= 15; i++) w *= i;
cout << w;
Pokaż odpowiedź
1.30767e+1215! = 1 307 674 368 000. double wypisuje domyślnie 6 cyfr znaczących w zapisie naukowym: 1.30767 · 10¹².
Najmniejszy typ dla 20!? Co wypisze fragment?
int n = 20;
if (n <= 12) cout << "int";
else if (n <= 20) cout << "long long";
else cout << "za duzo";
Pokaż odpowiedź
long long20! ≈ 2,4 · 10¹⁸ — za dużo dla int, ale wciąż mieści się w long long.
Ć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 →

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!

tablica.cpp
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";
▶ Wyjście
120 3628800 2432902008176640000

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.

pierwsze pudełka tablicy f: f[5] = 120, czyli 5! — i każde pudełko to poprzednie razy swój numer

Wiele pytań — jedna tablica

pytania.cpp
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
}
▶ Wejście
4 3 0 20 7
▶ Wyjście
6 1 2432902008176640000 5040

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.

iloraz.cpp
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
▶ Wyjście
42 999000

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.

silnie_cyfr.cpp
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";
▶ Wejście 1
145
▶ Wyjście 1
145 TAK
▶ Wejście 2
2022
▶ Wyjście 2
7 NIE

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

lancuch.cpp
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";
▶ Wyjście
69 -> 363600 -> 1454 -> 169 -> 363601 -> 1454 (powtórka)

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.

silniowy.cpp
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";
▶ Wyjście
3 4 1 0 1
ixx / i!x % i!
54633103
410347
3711
2101
1110

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.

Zajrzyj dalej: silnia jako funkcja i rekurencja Wzór n! = (n − 1)! · n mówi, że silnię można zdefiniować „samą sobą”. W lekcjach Funkcje i Rekurencja zapiszesz to dosłownie: 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ę.
Sprawdź się w głowie

Najpierw odpowiedz w myślach — wypisz sobie na kartce kolejne wartości zmiennych — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
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ź
568! / 6! = 7 · 8 = 56.
Co wypisze ten fragment?
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ź
73! + 0! = 6 + 1 = 7. Pamiętaj: f[0] = 1, a nie 0.
Co wypisze ten fragment?
long long w = 1;
for (long long i = 99; i <= 100; i++) w *= i;
cout << w;
Pokaż odpowiedź
9900100! / 98! = 99 · 100 = 9900.
Co wypisze ten fragment?
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ź
405854! + 0! + 5! + 8! + 5! = 24 + 1 + 120 + 40 320 + 120 = 40 585 — to właśnie jedna z czterech „liczb silniowych”.
Co wypisze ten fragment?
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ź
3Cyfry 1, 0, 0: 1! + 0! + 0! = 1 + 1 + 1 = 3.
Jak zapisać 10 w systemie silniowym? Co wypisze fragment?
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ź
12010 = 1 · 3! + 2 · 2! + 0 · 1! = 6 + 4 + 0. Cyfry: 1, 2, 0.
Co wypisze ten fragment?
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ź
2020! / 19! = 20 — wszystkie czynniki od 1 do 19 się skracają.
Co wypisze ten fragment?
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ź
1451! + 4! + 5! = 1 + 24 + 120 = 145 — sama liczba 145.
Ć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 →

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

nn!ostatnia cyfra
011
111
222
366
4244
51200
67200
75 0400

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.

reszta_po_kroku.cpp
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";
}
▶ Wyjście
i = 1: w = 1 i = 2: w = 2 i = 3: w = 6 i = 4: w = 3 i = 5: w = 1 i = 6: w = 6
iprawdziwe i!i! % 7w · i % 7
3662 · 3 % 7 = 6
42436 · 4 % 7 = 3
512013 · 5 % 7 = 1
672061 · 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

mod_1e9_7.cpp
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";
}
▶ Wyjście
20! mod p = 146326063 1000000! mod p = 641102369

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

olbrzym_mod.cpp
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";
}
▶ Wejście 1
1000000000000000000 999983
▶ Wyjście 1
0
▶ Wejście 2
6 7
▶ Wyjście 2
6

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

suma_mod.cpp
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";
▶ Wyjście
182527981
nie_dziel.cpp
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
▶ Wyjście
0 6

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ń

tablica_reszt.cpp
#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;
}
▶ Wejście
3 5 1000000 0
▶ Wyjście
120 641102369 1

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)! % ppierwsza?
211tak
322tak
462nie
5244tak
61200nie
77206tak
85 0400nie
113 628 80010tak

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.

Sprawdź się w głowie

Najpierw odpowiedz w myślach — wypisz sobie na kartce kolejne wartości zmiennych — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
long long w = 1;
for (int i = 1; i <= 4; i++) w = w * i % 10;
cout << w;
Pokaż odpowiedź
44! = 24, ostatnia cyfra 4.
Co wypisze ten fragment?
long long w = 1;
for (int i = 1; i <= 12; i++) w = w * i % 10;
cout << w;
Pokaż odpowiedź
0Od 5! ostatnią cyfrą jest 0 i tak już zostaje.
Co wypisze ten fragment?
long long w = 1;
for (int i = 1; i <= 5; i++) w = w * i % 7;
cout << w;
Pokaż odpowiedź
15! = 120 = 17 · 7 + 1.
Co wypisze ten fragment?
long long n = 100, m = 97;
if (n >= m) cout << 0;
else cout << "licz";
Pokaż odpowiedź
0100 ≥ 97, więc 97 jest jednym z czynników 100! — reszta to 0.
Co wypisze ten fragment?
long long w = 1;
for (int i = 1; i <= 4; i++) w = w * i % 8;
cout << w;
Pokaż odpowiedź
04! = 24 = 3 · 8. Zero wyszło, choć 4 < 8 — bo 8 = 2 · 4, a oba te czynniki są w 4!.
Co wypisze ten fragment?
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ź
531 + 2 + 6 + 24 + 120 = 153, a dwie ostatnie cyfry to 53.
Co wypisze ten fragment?
long long w = 1;
for (int i = 1; i <= 10; i++) w = w * i % 11;
cout << w;
Pokaż odpowiedź
1011 jest pierwsza, więc z twierdzenia Wilsona 10! daje resztę 11 − 1 = 10.
Co wypisze ten fragment?
int m = 7;
cout << (720 % m) / (120 % m) << " " << 720 / 120 % m;
Pokaż odpowiedź
6 6Uwaga, tu akurat wyszło dobrze: 720 % 7 = 6 i 120 % 7 = 1, a 6 / 1 = 6. Ale to przypadek — w poprzednim przykładzie (1 / 6) dzielenie reszt dało zły wynik. Nie dziel 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 →

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.

liczbadwójkipiątki
21—
4 = 2 · 22—
5—1
6 = 2 · 31—
8 = 2 · 2 · 23—
10 = 2 · 511
razem w 10!82

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.

Dwójki i piątki w liczbach od 1 do n
n = 25
Suwak działa po włączeniu JavaScriptu.

Liczymy piątki — sposób pierwszy

piatki_wolno.cpp
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";
▶ Wejście 1
25
▶ Wyjście 1
6
▶ Wejście 2
100
▶ Wyjście 2
24

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?

ndwójki w n!piątki w n!zera
10822
252266
100972424
1000994249249

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.

zera_szybko.cpp
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";
▶ Wejście 1
100
▶ Wyjście 1
24
▶ Wejście 2
1000000000000000000
▶ Wyjście 2
249999999999999995

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

legendre.cpp
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";
▶ Wyjście
trojek w 10!: 4 siodemek w 100!: 16

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

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

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

n2021–23242526–2930
zera w n!444667

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

Sprawdź się w głowie

Najpierw odpowiedz w myślach — wypisz sobie na kartce kolejne wartości zmiennych — a dopiero potem kliknij „Pokaż odpowiedź”.

Co wypisze ten fragment?
long long n = 50, zera = 0;
while (n > 0) {
    n /= 5;
    zera += n;
}
cout << zera;
Pokaż odpowiedź
1250 / 5 = 10 i 50 / 25 = 2 — razem 12 zer na końcu 50!.
Co wypisze ten fragment?
int x = 250, ile = 0;
while (x % 5 == 0) {
    ile++;
    x /= 5;
}
cout << ile;
Pokaż odpowiedź
3250 = 2 · 5 · 5 · 5 — trzy piątki.
Co wypisze ten fragment?
long long n = 24, zera = 0;
while (n > 0) {
    n /= 5;
    zera += n;
}
cout << zera;
Pokaż odpowiedź
424 / 5 = 4, 24 / 25 = 0. Cztery piątki: z 5, 10, 15 i 20.
Co wypisze ten fragment?
long long n = 10, e = 0;
while (n > 0) {
    n /= 2;
    e += n;
}
cout << e;
Pokaż odpowiedź
8Dwójki w 10!: 10 / 2 + 10 / 4 + 10 / 8 = 5 + 2 + 1 = 8.
Co wypisze ten fragment?
long long n = 125, zera = 0;
while (n > 0) {
    n /= 5;
    zera += n;
}
cout << zera;
Pokaż odpowiedź
31125 / 5 + 125 / 25 + 125 / 125 = 25 + 5 + 1 = 31.
Ile zer na końcu ma iloczyn 8 · 125 · 7? Co wypisze fragment?
long long x = 8LL * 125 * 7;
int zera = 0;
while (x % 10 == 0) {
    zera++;
    x /= 10;
}
cout << zera;
Pokaż odpowiedź
38 = 2³ i 125 = 5³ — trzy pary 2 · 5. Iloczyn to 7000.
Co wypisze ten fragment?
long long n = 7, p = 7, e = 0;
while (n > 0) {
    n /= p;
    e += n;
}
cout << e;
Pokaż odpowiedź
17! zawiera siódemkę dokładnie raz — w samej liczbie 7.
Czy jakaś silnia kończy się dokładnie 5 zerami? Co wypisze fragment?
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ź
nie24! ma 4 zera, a 25! już 6 — przy 25 przybywają dwa zera naraz.
Ć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 →

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:

c[0] to cyfra jedności (zielona — ostatnia cyfra liczby), c[6] to pierwsza cyfra liczby (niebieska). Czytamy od prawej: 3 628 800.

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

krokcyfra · 7 + przeniesienienowa cyfraprzeniesienie
c[0]0 · 7 + 0 = 000
c[1]2 · 7 + 0 = 1441
c[2]7 · 7 + 1 = 5005
konieczostało 550

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

Mnożenie pisemne w vectorze cyfr
Animacja działa po włączeniu JavaScriptu.
razy_liczba.cpp
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";
▶ Wyjście
5040

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

silnia_olbrzym.cpp
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";
▶ Wejście 1
25
▶ Wyjście 1
15511210043330985984000000
▶ Wejście 2
50
▶ Wyjście 2
30414093201713378043612608166064768844377641568960512000000000000

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

olbrzym_statystyki.cpp
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";
▶ Wyjście
cyfr: 158 suma cyfr: 648 zera na koncu: 24 ostatnia niezerowa: 4

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

suma_olbrzymow.cpp
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";
▶ Wyjście
16158688114800553828940313

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.

log10.cpp
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";
▶ Wyjście
0.0000 0.9542 1.0000 2.6990 2.9996 3.0000 6.5598

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.

cyfry_log.cpp
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";
    }
}
▶ Wyjście
10! ma 7 cyfr 100! ma 158 cyfr 1000! ma 2568 cyfr 1000000! ma 5565709 cyfr

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

pierwsza_cyfra.cpp
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";
    }
}
▶ Wyjście
10!: 3, trzy cyfry: 362 100!: 9, trzy cyfry: 933 1000!: 4, trzy cyfry: 402 1000000!: 8, trzy cyfry: 826

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

Logarytm podaje tylko początek 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ć.
Sprawdź się w głowie

Najpierw odpowiedz w myślach — wypisz sobie na kartce kolejne wartości zmiennych — a dopiero potem kliknij „Pokaż odpowiedź”.

Jaką liczbę trzyma ten vector? Co wypisze fragment?
vector<int> c = {4, 2, 0, 1};
for (int j = (int)c.size() - 1; j >= 0; j--) cout << c[j];
Pokaż odpowiedź
1024Cyfry od końca: c[0] = 4 to jedności, c[3] = 1 to tysiące. Wypisujemy od tyłu: 1024.
Co wypisze ten fragment?
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ź
1 0025 · 4 = 100: po pętli c = {0, 0}, a przeniesienie p = 1 — jeszcze trzeba je dopisać na koniec vectora.
Co wypisze ten fragment?
int x = 9 * 13 + 4;
cout << x % 10 << " " << x / 10;
Pokaż odpowiedź
1 12Cyfra 9 razy 13 plus przeniesienie 4 to 121: zostaje cyfra 1, a przeniesienie to 12 — dwucyfrowe, dlatego po pętli jest while, a nie if.
Co wypisze ten fragment?
cout << (long long)floor(log10(99999)) + 1;
Pokaż odpowiedź
599 999 leży między 10⁴ a 10⁵, log10 to około 4,99996 — w dół 4, plus 1: pięć cyfr.
Co wypisze ten fragment?
cout << log10(100) + log10(1000);
Pokaż odpowiedź
52 + 3 = 5, bo 100 · 1000 = 100 000 = 10⁵.
Co wypisze ten fragment?
double L = 0;
for (int i = 1; i <= 5; i++) L += log10(i);
cout << (long long)floor(L) + 1;
Pokaż odpowiedź
3Suma logarytmów to log10(5!) = log10(120) ≈ 2,079. Liczba cyfr: 2 + 1 = 3.
Co wypisze ten fragment?
double L = log10(3628800);
double f = L - floor(L);
cout << (int)pow(10, f + 1);
Pokaż odpowiedź
36L ≈ 6,5598, więc f ≈ 0,5598, a 10^(f + 1) ≈ 36,288 — część całkowita to dwie pierwsze cyfry liczby 3 628 800.
Co wypisze ten fragment?
vector<int> c = {0, 0, 0, 2, 7};      // 72000
int zera = 0;
while (c[zera] == 0) zera++;
cout << zera << " " << c[zera];
Pokaż odpowiedź
3 2Trzy zera na początku vectora to trzy zera na końcu liczby 72 000. Ostatnia niezerowa cyfra to 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 →

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

podium.cpp
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";
▶ Wyjście
336

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

kody.cpp
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";
▶ Wyjście
1000 720

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.

Symbol Newtona Liczba sposobów wybrania k rzeczy spośród n, gdy kolejność się nie liczy, to 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.

dwumian.cpp
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";
}
▶ Wyjście
i = 1: c = 8 i = 2: c = 36 i = 3: c = 120
ic · (n − k + i)/ ito jest
11 · 8 = 88C(8, 1)
28 · 9 = 7236C(9, 2)
336 · 10 = 360120C(10, 3)
dwumian_zle.cpp
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";
▶ Wyjście
96

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.

lotto.cpp
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";
▶ Wyjście
Lotto: 13983816 C(60, 30) = 118264581564861424

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

Trójkąt Pascala, wiersze od 0 do 6. Zaznaczona liczba C(5, 2) = 10 to suma dwóch niebieskich liczb nad nią: 4 + 6.

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.

pascal.cpp
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";
}
▶ Wyjście
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1

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

anagramy.cpp
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";
▶ Wejście 1
mama
▶ Wyjście 1
6
▶ Wejście 2
mississippi
▶ Wyjście 2
34650

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

PPGPGtrasa PPGPG: 3 × P i 2 × G

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.

Ściąga liczenia sposobów Wszystkie n rzeczy w rzędzie: 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).
Sprawdź się w głowie

Najpierw odpowiedz w myślach — wypisz sobie na kartce kolejne wartości zmiennych — a dopiero potem kliknij „Pokaż odpowiedź”.

Na ile sposobów 5 osób zajmie 2 miejsca na podium? Co wypisze fragment?
long long w = 1;
for (int i = 5; i > 3; i--) w *= i;
cout << w;
Pokaż odpowiedź
205 · 4 = 20 — dwa czynniki, od 5 w dół.
Ile uścisków dłoni wymieni 10 osób? Co wypisze fragment?
long long n = 10;
cout << n * (n - 1) / 2;
Pokaż odpowiedź
45C(10, 2) = 10 · 9 / 2 = 45.
Co wypisze ten fragment?
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ź
15C(6, 2) = 6 · 5 / 2 = 15. Kroki: 1 · 5 / 1 = 5, potem 5 · 6 / 2 = 15.
Co wypisze ten fragment?
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ź
1C(7, 7) = 1 — wszystkich siedmiu wybierasz na jeden sposób. W pętli wychodzi 7! / 7! = 1.
Co wypisze ten fragment?
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ź
6Wiersz 4 to 1 4 6 4 1, a t[4][2] = C(4, 2) = 3 + 3 = 6.
Ile słów da się ułożyć z liter słowa „tata”? Co wypisze fragment?
cout << 24 / (2 * 2);
Pokaż odpowiedź
64! = 24, a litery t i a powtarzają się po 2 razy: 24 / (2! · 2!) = 6.
Ile tras jest na kratce 2 × 2? Co wypisze fragment?
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ź
6C(4, 2) = 6: PPGG, PGPG, PGGP, GPPG, GPGP, GGPP.
Ile jest 4-cyfrowych kodów z różnych cyfr? Co wypisze fragment?
long long w = 1;
for (int i = 0; i < 4; i++) w *= 10 - i;
cout << w;
Pokaż odpowiedź
504010 · 9 · 8 · 7 = 5040.
Co wypisze ten fragment?
long long c = 1;
for (long long i = 1; i <= 3; i++) c *= (6 - 3 + i) / i;
cout << c;
Pokaż odpowiedź
16Błędna kolejność: 4 / 1 = 4, 5 / 2 = 2, 6 / 3 = 2, czyli 4 · 2 · 2 = 16. Prawdziwe C(6, 3) to 20 — najpierw mnożymy, potem dzielimy!
Ć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 →

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

Jak rozwiązywać zadania z silnią 1) Sprawdź ograniczenia: jeśli n ≤ 20, możesz liczyć silnię wprost w 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.
łatwe

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.

1 Turniej każdy z każdymłatwe✓ zaliczone Ile partii w turnieju każdy z każdym i ile możliwych tabel końcowych? n · (n − 1) / 2n!long long Rozwiąż 2 Pary na balułatwe✓ zaliczone Ile sposobów na n par chłopak–dziewczyna i na rząd do zdjęcia „na przemian”? n!2 · n! · n!mnożymy możliwości Rozwiąż 3 Matematyka przed fizykąłatwe✓ zaliczone Plan n lekcji, w którym matematyka jest gdzieś przed fizyką — dokładnie połowa wszystkich. n! / 2symetriapary planów Rozwiąż 4 Dyżurniłatwe✓ zaliczone Dwóch dyżurnych z równymi prawami albo główny i zastępca — kiedy kolejność ma znaczenie? n · (n − 1)dzielimy przez 2long long Rozwiąż 5 Seria na półcełatwe✓ zaliczone Tomy serii stoją razem i po kolei — sklej je w jedną grubą książkę. sklejanie(n − k + 1)!long long Rozwiąż 6 Silnie w przedzialełatwe✓ zaliczone Ile różnych silni leży w przedziale [a, b]? Jedynkę liczymy raz. silnie do 19!a ≤ f ≤ blicznik Rozwiąż 7 Ostatnia cyfra sumy silniłatwe✓ zaliczone Ostatnia cyfra 1! + 2! + … + n! dla n do 10¹⁸ — od 5! dalej same zera. % 10min(n, 4)od 5! zero na końcu Rozwiąż 8 Czy k dzieli n!?łatwe✓ zaliczone Dla każdej pary: czy n! dzieli się przez k bez reszty? Tablica silni i %. tablica silnif[n] % k == 0long long Rozwiąż 9 Silnia z odstępamiłatwe✓ zaliczone Wypisz n! z cyframi w grupach po trzy: 3 628 800. to_string i spacje co trzy cyfry od końca. to_stringgrupy po 3 cyfry(s.size() - i) % 3 Rozwiąż 10 10! sekundłatwe✓ zaliczone 10! sekund to dokładnie 6 tygodni. Zamień n! sekund na tygodnie, dni, godziny, minuty i sekundy. dzielenie z resztą604 800 s w tygodniulong long Rozwiąż
średnie

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

11 Zera iloczynu dwóch silniśrednie✓ zaliczone Iloma zerami kończy się a! · b!? Piątki obu silni się sumują. n / 5 + n / 25 + …piątki się sumująlong long Rozwiąż 12 Pary na wycieczkęśrednie✓ zaliczone Na ile sposobów 2n uczniów może podzielić się na pary? (2n − 1) · (2n − 3) · … · 1. silnia podwójna(2n − 1)!!pierwszy wybiera parę Rozwiąż 13 Samorząd klasowyśrednie✓ zaliczone Przewodniczący, zastępca i k-osobowa komisja: n · (n − 1) · C(n − 2, k). role z kolejnościąC(n − 2, k)mnożymy etapy Rozwiąż 14 Trafienia w lottośrednie✓ zaliczone Ile zakładów ma dokładnie t trafień? C(k, t) · C(n − k, k − t). C(k, t)C(n − k, k − t)dwie grupy liczb Rozwiąż 15 Droga do szkołyśrednie✓ zaliczone Wszystkie trasy minus trasy przez rozkopane skrzyżowanie. C(a + b, a)odejmowanie złych trastrasy przez punkt Rozwiąż 16 Mikołajkiśrednie✓ zaliczone Ile losowań, w których nikt nie wylosował siebie? D(n) = (n − 1) · (D(n − 1) + D(n − 2)). nieporządkidwie poprzednie wartościlong long Rozwiąż 17 Rozkład silni na czynnikiśrednie✓ zaliczone Wypisz n! jako 2^8 * 3^4 * 5^2 * 7^1 — sito i wzór Legendre’a. sito Eratostenesan / p + n / p² + …separator * Rozwiąż 18 Numer ustawieniaśrednie✓ zaliczone Który w kolejności słownikowej jest ten układ liczb 1..n? Licz bloki po (n − 1)!, (n − 2)!, … permutacjebloki po (n − 1)!mniejsze niewykorzystane Rozwiąż 19 Iloczyn silni modulośrednie✓ zaliczone 1! · 2! · … · n! mod 10⁹ + 7 — bieżąca silnia i bieżący iloczyn w jednej pętli. f = f * i % MODw = w * f % MODdwa akumulatory Rozwiąż 20 Silnia z d cyframiśrednie✓ zaliczone Najmniejsze n, którego silnia ma co najmniej d cyfr — logarytmy dokładane po kolei. log10floor(L) + 1 >= dpętla aż do skutku Rozwiąż
trudne

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.

21 Ostatnia niezerowa cyfra olbrzymatrudne✓ zaliczone n do miliona: usuń z iloczynu pary 2 · 5, resztę mnóż modulo 10. usuń dwójki i piątkiw = w * x % 10nadmiar dwójek Rozwiąż 22 Zera w innym systemietrudne✓ zaliczone Zera na końcu n! w systemie o podstawie b: rozłóż b i weź najrzadszy czynnik. rozkład b na czynnikiwzór Legendre’amin po czynnikach Rozwiąż 23 Najmniejsza silnia podzielna przez ktrudne✓ zaliczone Najmniejsze n, dla którego k dzieli n! — dla każdego czynnika p^e zbieraj p-ki po wielokrotnościach p. rozkład k na czynnikiwielokrotności pmax po czynnikach Rozwiąż 24 Ile dzielników ma silnia?trudne✓ zaliczone Liczba dzielników n! to (e₁ + 1) · (e₂ + 1) · … — sito, Legendre i modulo. sitowykładniki z Legendre’a(e + 1) · … Rozwiąż 25 Numer słowa w słownikutrudne✓ zaliczone Który alfabetycznie jest ten anagram swoich liter? Numer ustawienia z powtórzeniami. liczniki literm! / (a! · b! · …)mniejsze litery najpierw Rozwiąż 26 Cukierki dla dziecitrudne✓ zaliczone n jednakowych cukierków dla k dzieci: gwiazdki i kreski, czyli C(n + k − 1, k − 1). gwiazdki i kreskiC(n + k − 1, k − 1)każdy co najmniej 1 Rozwiąż 27 Pierwsze trzy cyfry olbrzymatrudne✓ zaliczone Trzy pierwsze cyfry n! dla n do miliona: (int)pow(10, f + 2). log10część ułamkowapow(10, f + 2) Rozwiąż 28 Wielki finał: kalkulator silnitrudne✓ zaliczone Sześć poleceń w jednym programie: silnia, zera, modulo, cyfry, dwumian i „czy to silnia?”. wszystko z lekcjitablica logarytmówstring z poleceniem Rozwiąż

Częste błędy i dobre praktyki

1️⃣
Start od jedynki
Iloczyn zaczyna się od w = 1, a nie od 0 — zero pomnożone przez cokolwiek zostaje zerem. Suma startuje od 0, iloczyn od 1.
🎯
i <= n, a nie i < n
Z warunkiem i < n pętla nie pomnoży przez samo n i policzy (n − 1)!. Sprawdzaj program na małym n, którego silnię znasz: 5! = 120.
0️⃣
0! = 1
To nie pomyłka, tylko umowa, dzięki której działają wzory. Pętla od 1 do 0 nie wykona się ani razu i zostawi 1 — dobrze. W tablicy silni pamiętaj o f[0] = 1.
➖
Ujemne n
Silnia liczby ujemnej nie istnieje, a pętla dla ujemnego n też zostawi 1. Gdy w danych mogą być liczby ujemne, wyłap je if-em przed pętlą.
💥
12 i 20 to granice
int mieści silnie do 12!, long long do 20!. Powyżej wynik jest bzdurą (czasem nawet ujemną), a program nie zgłosi błędu. Duże n w zadaniu oznacza inne pytanie.
🔁
Reset dla każdej liczby
Gdy liczysz silnię dla wielu liczb, ustaw w = 1 wewnątrz pętli po liczbach. Inaczej wynik poprzedniej liczby „przecieknie” do następnej.
❗
Wykrzyknik to nie silnia
W C++ !n to zaprzeczenie: !5 to 0. Zapis 5! się nie skompiluje. Silnię zawsze liczysz sam — pętlą albo tablicą.
🧮
Modulo w long long
W w = w * i % MOD iloczyn liczy się przed resztą — przy int przepełni się, zanim reszta zdąży pomóc. Zmienna z wynikiem modulo zawsze w long long.
🚫
Nie dziel reszt
n! / k! modulo m licz pętlą od k + 1 do n, a C(n, k) modulo — trójkątem Pascala. Dzielenie reszt daje zupełnie zły wynik.
5️⃣
Zera to piątki
Zer na końcu n! jest tyle, ile piątek: n/5 + n/25 + …. Licz to dzieleniem n w pętli, a nie potęgami piątki, które mogą przekroczyć zakres.
↩️
Olbrzym od końca
Cyfry olbrzyma trzymaj od jedności (c[0]), nowe cyfry dokładaj push_back, a na koniec wypisuj od tyłu. Po mnożeniu dopisz całe przeniesienie — pętlą while.
📐
Najpierw mnóż, potem dziel
W symbolu Newtona pisz c = c * (n - k + i) / i. Zapis c *= (n - k + i) / i najpierw dzieli i gubi resztę.

Co dalej?

Silnia to pierwsza naprawdę wielka liczba, z którą zmierzyłeś się w kursie — i od razu poznałeś cztery sposoby, żeby ją okiełznać: modulo, liczenie czynników, mnożenie pisemne i logarytmy. Drzewko wyborów, symbol Newtona i trójkąt Pascala zostaną z Tobą aż do olimpiady, bo kombinatoryka pojawia się w zadaniach bardzo często. Następna lekcja to ostatnie narzędzie matematyczne tego etapu: wartość bezwzględna. A jeśli chcesz trenować z mentorami — dołącz do T-Olimpians.