Factorial — AlgoClar

De ce contează?

Câte aranjamente diferite poți face cu 5 cărți puse în rând? La prima poziție ai 5 variante, la a doua 4 rămase, apoi 3, 2, 1 — în total 5·4·3·2·1 = 120. Acest produs al primelor numere are un nume: factorial.

Ce este factorialul

n! (n factorial) este produsul tuturor numerelor de la 1 la n:

n! = 1 · 2 · 3 · ... · n, iar 0! = 1 (prin convenție)

Exemple: 3! = 6, 4! = 24, 5! = 120. Crește foarte repede.

Algoritm pas cu pas: 5!

`i`	înmulțim	`rezultat`
start	—	1
2	1·2	2
3	2·3	6
4	6·4	24
5	24·5	120

Implementare iterativă

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long rezultat = 1;          // long long: factorialul creste rapid
    for (int i = 2; i <= n; i++) {
        rezultat *= i;
    }
    cout << rezultat << "\n";        // 5 -> 120
    return 0;
}

Observația-cheie

Pornim de la 1 (nu de la 0!) — altfel produsul ar fi mereu 0. Bucla poate începe de la 2, fiindcă înmulțirea cu 1 nu schimbă nimic.

Cât de repede crește (de ce e periculos)

`n`	n!	încape în
10	3.628.800	int
12	479.001.600	int (la limită)
13	6.227.020.800	doar long long
20	~2,4 · 10¹⁸	long long (la limită)
21	~5,1 · 10¹⁹	nici long long

Observația-cheie

Pentru n ≥ 21, nici long long nu mai ajunge. Problemele cer atunci fie numere mari (big integer), fie rezultatul modulo un număr prim.

Varianta modulo un număr prim

Când problema cere n! % M, aplici modulo după fiecare înmulțire ca să nu se spargă:

const long long M = 1000000007;     // numar prim folosit des
long long fact = 1;
for (int i = 2; i <= n; i++) {
    fact = (fact * i) % M;          // modulo la fiecare pas
}
// fact contine acum n! modulo M

Complexitate

Caz	Timp	Spațiu
oricare	O(n)	O(1)

O singură buclă de la 2 la n.

Greșeli frecvente

Capcane reale la factorial:

int în loc de long long: 13! deja se sparge. Folosește long long, iar pentru n mare lucrează modulo.
Inițializezi cu 0: rezultat = 0 face produsul mereu 0. Pornește de la 1.
Overflow chiar și cu modulo greșit aplicat: dacă aduni modulo doar la final, valoarea s-a spart deja. Aplică % M după fiecare înmulțire.
Recursivitate adâncă: varianta recursivă pe n foarte mare poate da stack overflow; cea iterativă e mai sigură.

De reținut

n! = 1·2·...·n, cu 0! = 1; pornește acumulatorul de la 1.
Crește exploziv: long long de la n ≥ 13, iar peste 20 ai nevoie de modulo sau numere mari.
Pentru n! modulo M, aplică % M după fiecare înmulțire.