Factorial módulo $p$

En algunos casos es necesario considerar fórmulas complejas módulo algún primo $p$, que contienen factoriales tanto en el numerador como en el denominador, como las que se encuentran en la fórmula de los coeficientes binomiales. Consideramos el caso en que $p$ es relativamente pequeño. Este problema solo tiene sentido cuando los factoriales aparecen tanto en el numerador como en el denominador de fracciones. En caso contrario $p!$ y los términos posteriores se reducirán a cero. Pero en las fracciones los factores de $p$ se pueden cancelar, y la expresión resultante será no nula módulo $p$.

Así, de forma formal la tarea es: se quiere calcular $n! \bmod p$, sin tener en cuenta todos los factores múltiples de $p$ que aparecen en el factorial. Imaginemos que se escribe la factorización prima de $n!$, se quitan todos los factores $p$ y se calcula el producto módulo $p$. Denotaremos este factorial modificado con $n!${%p}n!%p​. Por ejemplo $7!${%p} \equiv 1 \cdot 2 \cdot \underbrace{1}{3} \cdot 4 \cdot 5 \underbrace{2}{6} \cdot 7 \equiv 2 \bmod 3.

Aprender a calcular de forma efectiva este factorial modificado nos permite calcular rápidamente el valor de varias fórmulas combinatorias (por ejemplo, coeficientes binomiales).

Algoritmo

Escribamos este factorial modificado de forma explícita.

\begin{eqnarray} n!{%p} &=& 1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-2) \cdot (p-1) \cdot \underbrace{1}{p} \cdot (p+1) \cdot (p+2) \cdot \ldots \cdot (2p-1) \cdot \underbrace{2}{2p} \
& &\quad \cdot (2p+1) \cdot \ldots \cdot (p^2-1) \cdot \underbrace{1}{p^2} \cdot (p^2 +1) \cdot \ldots \cdot n \pmod{p} \\ &=& 1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-2) \cdot (p-1) \cdot \underbrace{1}{p} \cdot 1 \cdot 2 \cdot \ldots \cdot (p-1) \cdot \underbrace{2}{2p} \cdot 1 \cdot 2 \
& &\quad \cdot \ldots \cdot (p-1) \cdot \underbrace{1}_{p^2} \cdot 1 \cdot 2 \cdot \ldots \cdot (n \bmod p) \pmod{p} \end{eqnarray}

Se ve claramente que el factorial se divide en varios bloques de la misma longitud excepto el último.

\begin{eqnarray} n!{%p}&=& \underbrace{1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-2) \cdot (p-1) \cdot 1}{1\text{st}} \cdot \underbrace{1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-2) \cdot (p-1) \cdot 2}{2\text{nd}} \cdot \ldots \\ & & \cdot \underbrace{1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-2) \cdot (p-1) \cdot 1}{p\text{th}} \cdot \ldots \cdot \quad \underbrace{1 \cdot 2 \cdot \cdot \ldots \cdot (n \bmod p)}_{\text{tail}} \pmod{p}. \end{eqnarray}

La parte principal de los bloques es fácil de contar: es simplemente $(p-1)!\ \mathrm{mod}\ p$. Podemos calcularlo de forma programática o simplemente aplicar el teorema de Wilson, que afirma que $(p-1)! \bmod p = -1$ para cualquier primo $p$.

Tenemos exactamente $\lfloor \frac{n}{p} \rfloor$ de esos bloques, por lo tanto hay que elevar $-1$ a la potencia $\lfloor \frac{n}{p} \rfloor$. Esto se puede hacer en tiempo logarítmico usando exponenciación binaria; sin embargo también se puede notar que el resultado alternará entre $-1$ y $1$, así que solo hay que mirar la paridad del exponente y multiplicar por $-1$ si la paridad es impar. Y en lugar de una multiplicación, también podemos simplemente restar el resultado actual de $p$.

El valor del último bloque parcial se puede calcular por separado en $O(p)$.

Esto deja solo el último elemento de cada bloque. Si ocultamos los elementos ya tratados, podemos ver el siguiente patrón:

$$n!_{$$

Esto de nuevo es un factorial modificado, solo que con una dimensión mucho menor. Es $\lfloor n / p \rfloor !_{$.

Así, durante el cálculo del factorial modificado $n!${%p}n%p​ hicimos $O(p)$ operaciones y nos queda el cálculo de $\lfloor n / p \rfloor !${%p}. Tenemos una fórmula recursiva. La profundidad de la recursión es $O(\log_p n)$, y por lo tanto el comportamiento asintótico completo del algoritmo es $O(p \log_p n)$.

Nótese que, si se precomputan los factoriales $0!,~ 1!,~ 2!,~ \dots,~ (p-1)!$ módulo $p$, entonces la complejidad será solo $O(\log_p n)$.

Implementación

No necesitamos recursión porque este es un caso de recursión de cola y por lo tanto se puede implementar fácilmente usando iteración. En la siguiente implementación precomputamos los factoriales $0!,~ 1!,~ \dots,~ (p-1)!$, y así tenemos tiempo de ejecución $O(p + \log_p n)$. Si hay que llamar a la función varias veces, entonces se puede hacer la precomputación fuera de la función y hacer el cálculo de $n!_{$ en tiempo $O(\log_p n)$.

int factmod(int n, int p) {
    vector<int> f(p);
    f[0] = 1;
    for (int i = 1; i < p; i++)
        f[i] = f[i-1] * i % p;
 
    int res = 1;
    while (n > 1) {
        if ((n/p) % 2)
            res = p - res;
        res = res * f[n%p] % p;
        n /= p;
    }
    return res;
}

Como alternativa, si solo se tiene memoria limitada y no se puede almacenar todos los factoriales, también se pueden recordar solo los factoriales que se necesitan, ordenarlos, y luego calcularlos en una sola pasada computando los factoriales $0!,~ 1!,~ 2!,~ \dots,~ (p-1)!$ en un bucle sin almacenarlos de forma explícita.

Multiplicidad de $p$

Si queremos calcular un coeficiente binomial módulo $p$, entonces adicionalmente necesitamos la multiplicidad de $p$ en $n$, es decir, la cantidad de veces que $p$ aparece en la factorización prima de $n$, o la cantidad de veces que borramos $p$ durante el cálculo del factorial modificado.

La fórmula de Legendre  nos da una forma de calcular esto en tiempo $O(\log_p n)$. La fórmula da la multiplicidad $\nu_p$ como:

$$\nu_p(n!) = \sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor$$

Así obtenemos la implementación:

int multiplicity_factorial(int n, int p) {
    int count = 0;
    do {
        n /= p;
        count += n;
    } while (n);
    return count;
}

Esta fórmula se puede demostrar muy fácilmente usando las mismas ideas que en las secciones anteriores. Quitamos todos los elementos que no contienen el factor $p$. Esto deja $\lfloor n/p \rfloor$ elementos restantes. Si quitamos el factor $p$ de cada uno de ellos, obtenemos el producto $1 \cdot 2 \cdots \lfloor n/p \rfloor = \lfloor n/p \rfloor !$, y de nuevo tenemos una recursión.