Factoriales

¿Qué es un factorial?

El factorial de N (escrito $N!$) es el producto de todos los números del 1 al N:

$N! = 1 \times 2 \times 3 \times \cdots \times N$

Analogía: Si tienes 5 libros y quieres saber de cuántas formas puedes ordenarlos en un estante, la respuesta es $5! = 120$.

Valores importantes:

• $0! = 1$ (por convención)
• $1! = 1$
• $5! = 120$
• $10! = 3,628,800$
• $20! = 2,432,902,008,176,640,000$ (¡no cabe en int!)

Cálculo básico

// Iterativo
long long factorial(int n) {
    long long resultado = 1;
    for (int i = 2; i <= n; i++) {
        resultado *= i;
    }
    return resultado;
}

// Recursivo
long long factorialRec(int n) {
    if (n <= 1) return 1;
    return n * factorialRec(n - 1);
}

Factorial modular

Para problemas de competencia donde N puede ser muy grande:

const int MOD = 1e9 + 7;
const int MAXN = 1000005;
long long fact[MAXN], inv_fact[MAXN];

long long potencia(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) res = res * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return res;
}

void precalcular() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        fact[i] = fact[i - 1] * i % MOD;
    }

    inv_fact[MAXN - 1] = potencia(fact[MAXN - 1], MOD - 2, MOD);
    for (int i = MAXN - 2; i >= 0; i--) {
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD;
    }
}

Esto precalcula $n!$ e $(n!)^{-1}$ para todo $n$ hasta MAXN. Luego puedes calcular combinaciones en $O(1)$:

long long C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] % MOD * inv_fact[k] % MOD * inv_fact[n - k] % MOD;
}

Ceros finales del factorial

Problema clásico: ¿Cuántos ceros tiene $N!$ al final?

Los ceros al final vienen de factores de 10 = 2 × 5. Como siempre hay más 2's que 5's, contamos cuántos 5's hay:

int cerosFactorial(int n) {
    int ceros = 0;
    for (int p = 5; p <= n; p *= 5) {
        ceros += n / p;
    }
    return ceros;
}
// cerosFactorial(100) = 20 + 4 = 24

$100! = \ldots 00000000000000000000000000$ (24 ceros).

Ejercicio de práctica

Calcula $N! \mod (10^9+7)$ para un N dado.

Entrada: 10 Salida: 3628800

Entrada: 1000000 Salida: un número menor que $10^9+7$

#include <iostream>
using namespace std;

const int MOD = 1e9 + 7;

int main() {
    int n;
    cin >> n;

    long long resultado = 1;
    for (int i = 2; i <= n; i++) {
        resultado = resultado * i % MOD;
    }

    cout << resultado << endl;
    return 0;
}