1
1. Factorial — definitie si calcul iterativ
n! (n factorial) = produsul tuturor intregilor pozitivi de la 1 la n:
n! = 1 × 2 × 3 × … × n, cu conventia 0! = 1.
n! = 1 × 2 × 3 × … × n, cu conventia 0! = 1.
Valori uzuale:
0!=1 | 1!=1 | 5!=120 | 10!=3.628.800 | 12!=479.001.600
Factorialul creste extrem de rapid: 20! ≈ 2.4×1018, depasind long long abia la 21!.
Implementarea cea mai sigura este iterativa, O(n):
# Factorial iterativ - O(n) def factorial_iter(n): result = 1 for i in range(2, n + 1): result *= i return result for n in [0, 1, 5, 10, 12]: print(f"{n}! = {factorial_iter(n)}")
Output real (rulat cu python):
0! = 1 1! = 1 5! = 120 10! = 3628800 12! = 479001600
⚡ C++ — EXCLUSIV INTENSIV
In C++, long long permite n≤20. Pentru n mai mare se lucreaza modular.
#include <iostream> using namespace std; long long factorialIter(int n) { long long result = 1; for (int i = 2; i <= n; i++) result *= i; return result; } int main() { int ns[] = {0,1,5,10,12}; for (int n : ns) cout << n << "! = " << factorialIter(n) << endl; return 0; }
Output real (compilat g++ -std=c++17, rulat):
0! = 1 1! = 1 5! = 120 10! = 3628800 12! = 479001600
2
2. Formula Legendre — puterea unui prim in n!
Formula Legendre: Exponentul primului p in n! este:
vp(n!) = ⌊n/p⌋ + ⌊n/p2⌋ + ⌊n/p3⌋ + … (suma se opreste cand pk > n)
vp(n!) = ⌊n/p⌋ + ⌊n/p2⌋ + ⌊n/p3⌋ + … (suma se opreste cand pk > n)
Intuitie:
Fiecare multiplu de 5 din {1,...,10} contribuie un factor 5. Dar 25=52 contribuie doi, deci il numaram din nou la ⌊n/25⌋.
Aplicatia clasica: zerouri la finalul lui n! = v5(n!) (factorii de 2 sunt mereu mai multi decat cei de 5).
# Formula Legendre: exponentul primului p in n! def putere_prim_in_factorial(n, p): exp = 0 pk = p while pk <= n: exp += n // pk pk *= p return exp for n in [10, 20, 100]: print(f"Zerouri in {n}! = {putere_prim_in_factorial(n, 5)}") for p in [2, 3, 5, 7]: print(f"Puterea lui {p} in 20! = {putere_prim_in_factorial(20, p)}")
Output real (rulat cu python):
Zerouri in 10! = 2 Zerouri in 20! = 4 Zerouri in 100! = 24 Puterea lui 2 in 20! = 18 Puterea lui 3 in 20! = 8 Puterea lui 5 in 20! = 4 Puterea lui 7 in 20! = 2
⚡ C++ — EXCLUSIV INTENSIV — Atentie la overflow in pk!
Declarati long long pk. Pentru n=109 si p=2, pk poate depasi int dupa 30 de pasi.
#include <iostream> using namespace std; int putereInFactorial(int n, int p) { int exp = 0; long long pk = p; while (pk <= n) { exp += (int)(n/pk); pk *= p; } return exp; } int main() { cout << "zerouri in 100! = " << putereInFactorial(100,5) << endl; cout << "exp(5 in 10!) = " << putereInFactorial(10,5) << endl; return 0; }
Output real (compilat g++ -std=c++17, rulat):
zerouri in 100! = 24 exp(5 in 10!) = 2
Complexitate: O(logp n). Pentru n=109, p=2 → 30 iteratii.
3
3. Descompunerea completa a lui n! in factori primi
Combinand ciurul lui Eratostene cu formula Legendre obtinem toti factorii primi ai lui n! si exponentii lor.
# Descompunerea lui n! ca produs de prime def factorizare_factorial(n): sieve = list(range(n + 1)) for i in range(2, int(n**0.5) + 1): if sieve[i] == i: for j in range(i*i, n+1, i): if sieve[j] == j: sieve[j] = i rezultat = {} for p in range(2, n + 1): if sieve[p] == p: exp, pk = 0, p while pk <= n: exp += n // pk; pk *= p rezultat[p] = exp return rezultat for n in [10, 12]: d = factorizare_factorial(n) parts = [f"{p}^{e}" for p, e in sorted(d.items())] print(f"{n}! = " + " * ".join(parts))
Output real (rulat cu python):
10! = 2^8 * 3^4 * 5^2 * 7^1 12! = 2^10 * 3^5 * 5^2 * 7^1 * 11^1
Verificare: 2^8 x 3^4 x 5^2 x 7 = 256 x 81 x 25 x 7 = 3.628.800 ✓
Complexitate: O(n log log n) pentru ciur + O(pi(n) log n) pentru Legendre pe fiecare prim. Eficient pentru n ≤ 106.
4
4. Exponentiere rapida — Square and Multiply, O(log n)
Problema: Calculeaza ab % m pentru b pana la 1018. Varianta naiva (b inmultiri) e impracticabila.
Ideea: Scriem b in baza 2. Daca b=13=11012=8+4+1, atunci a13=a1×a4×a8.
Ideea: Scriem b in baza 2. Daca b=13=11012=8+4+1, atunci a13=a1×a4×a8.
Pas cu pas: 7^13
72=49, 74=2401, 78=5764801
713 = 71 × 74 × 78 = 96.889.010.407 (3 ridicari la patrat + 3 inmultiri vs 12 naive)
# Exponentiere rapida: base^exp % mod in O(log exp) def power_fast(base, exp, mod): result = 1 base %= mod while exp > 0: if exp % 2 == 1: result = result * base % mod base = base * base % mod exp //= 2 return result MOD = 1_000_000_007 print(f"2^10 mod M = {power_fast(2, 10, MOD)}") print(f"7^100 mod M = {power_fast(7, 100, MOD)}") print(f"2^1000000 mod M = {power_fast(2, 1_000_000, MOD)}")
Output real (rulat cu python):
2^10 mod M = 1024 7^100 mod M = 946501044 2^1000000 mod M = 235042059
⚡ C++ — EXCLUSIV INTENSIV
Aplica % mod dupa fiecare inmultire. Daca base~109 si mod~109, produsul intermediar~1018 e la limita long long.
#include <iostream> using namespace std; long long powerMod(long long base, long long exp, long long mod) { long long result = 1; base %= mod; while (exp > 0) { if (exp & 1) result = result * base % mod; base = base * base % mod; exp >>= 1; } return result; } int main() { long long M = 1000000007LL; cout << "2^10 mod M = " << powerMod(2,10,M) << endl; cout << "7^100 mod M = " << powerMod(7,100,M) << endl; return 0; }
Output real (compilat g++ -std=c++17, rulat):
2^10 mod M = 1024 7^100 mod M = 946501044
Complexitate: O(log exp) timp, O(1) spatiu. Pentru exp=1018 → 60 pasi.
5
5. Coeficienti binomiali modular EXCLUSIV INTENSIV
⚡ Sectiune exclusiv intensiv informatica — concursuri si olimpiada
Combinam exponentierea rapida cu inversul modular pentru a calcula C(n,k)%p fara factoriale uriase direct.
Inversul modular (Mica teorema Fermat): Daca p e prim si gcd(a,p)=1:
a-1 mod p = ap-2 mod p
Deci: C(n,k) mod p = n! × (k!)p-2 × ((n-k)!)p-2 mod p
a-1 mod p = ap-2 mod p
Deci: C(n,k) mod p = n! × (k!)p-2 × ((n-k)!)p-2 mod p
# C(n, k) mod p, pentru p prim MOD = 1_000_000_007 def power_fast(base, exp, mod): result, base = 1, base % mod while exp > 0: if exp & 1: result = result * base % mod base = base * base % mod; exp >>= 1 return result def factorial_mod(n, mod): r = 1 for i in range(2, n+1): r = r * i % mod return r def comb_mod(n, k, mod): if k > n: return 0 num = factorial_mod(n, mod) den = factorial_mod(k, mod) * factorial_mod(n-k, mod) % mod return num * power_fast(den, mod-2, mod) % mod print(f"C(5,2) = {comb_mod(5, 2, MOD)}") print(f"C(10,3) = {comb_mod(10, 3, MOD)}") print(f"C(1000,500) mod M = {comb_mod(1000, 500, MOD)}")
Output real (rulat cu python):
C(5,2) = 10 C(10,3) = 120 C(1000,500) mod M = 159835829
Optimizare pentru query-uri multiple: Precalculeaza fact[i]=i! mod p si inv_fact[i]=(i!)-1 mod p. Fiecare C(n,k) in O(1) dupa O(n) pregatire.
6
6. Tabel complexitati si capcane la BAC si olimpiada
Tabel rezumativ:
- Factorial iterativ: O(n) timp, O(1) spatiu. Sigur pana la n=20 cu long long.
- Factorial recursiv: O(n) timp, O(n) stiva. Risc stack overflow pentru n>10.000.
- Formula Legendre (un prim): O(logp n) timp.
- Descompunerea lui n! (toti primii): O(n log log n) ciur + O(pi(n) log n) Legendre.
- Exponentiere rapida: O(log exp) timp, O(1) spatiu.
Capcane frecvente la examen:
- Overflow silent C++: int max~2.1×109. 13!=6.2×109 depaseste. Folositi long long.
- pk overflow in Legendre: Declarati long long pk, nu int pk.
- Zerouri != n/5: n/5 uita multiplii de 25, 125 etc. Folositi formula Legendre completa.
- Modulul la exponentiere: Aplicati % mod dupa fiecare inmultire, nu la final.
Calcul mental rapid — zerouri in n!:
100!: 100/5=20, 100/25=4, 100/125=0 → 20+4 = 24 zerouri
1000!: 1000/5=200, 1000/25=40, 1000/125=8, 1000/625=1 → 249 zerouri