Fatorial módulo $p$ em $O(p \log n)$

Em alguns casos, é necessário considerar fórmulas complexas módulo $p$, contendo fatoriais no numerador e no denominador. Consideramos o caso em que $p$ é relativamente pequeno. Esse problema só faz sentido quando fatores são incluídos no numerador e no denominador das frações. Caso contrário $p!$ e os termos subsequentes serão reduzidos a zero, mas em frações, todos os multiplicadores contendo $p$ podem ser reduzidos, e a expressão resultante será diferente de zero com o módulo $p$.

Assim, formalmente a tarefa é: Calcular $n! \bmod p$, sem levar em consideração todos os múltiplos fatores de $p$ que aparecem no fatorial. A fatoração em primos de $n!$, remover todos os fatores $p$, e então calcular o produto módulo $p$. Denotaremos esse fatorial modificado como $n!_{\%p}$.

Aprender como calcular efetivamente esse fatorial modificado nos permite calcular rapidamente o valor de várias fórmulas combinatórias (por exemplo, coeficientes binomiais).

Algoritmo

Vamos escrever este fatorial explicitamente.

$$\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 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}$$

Pode-se ver claramente que o fatorial está dividido em vários blocos do mesmo tamanho exceto pelo ú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}$$

A parte geral dos blocos é apenas $(p-1)!\ \mathrm{mod}\ p$ que você pode calcular programaticamente ou através do teorema de Wilson, de acordo com o qual: $(p-1)! \bmod p = p-1$. Para multiplicar as partes comuns de todos os blocos, podemos exponenciar o valor para um índice mais elevado módulo $p$, o que pode ser feito em $O(\log n)$ operações usando Exponenciação Binária; no entanto, você pode perceber que o resultado sempre será $1$ ou $p-1$, dependendo da paridade do índice. O valor do último bloco parcial pode ser calculado separadamente em $O(p)$. Deixando apenas os últimos elementos dos blocos, podemos examinar que:

$$n!_{\%p} = \underbrace{ \ldots \cdot 1 } \cdot \underbrace{ \ldots \cdot 2} \cdot \ldots \cdot \underbrace{ \ldots \cdot (p-1)} \cdot \underbrace{ \ldots \cdot 1 } \cdot \underbrace{ \ldots \cdot 1} \cdot \underbrace{ \ldots \cdot 2} \cdots$$

E novamente, removendo os blocos que já calculamos, recebemos um fatorial "modificado", mas com uma dimensão menor ($\lfloor n / p \rfloor$ blocos restantes). Assim, no cálculo do "modificado", o fatorial $n!_{\%p}$, fizemos $O(p)$ operações e ficamos com o cálculo de $(n/p)!_{\%p}$. Nessa dependência recursiva, obtemos que a profundidade da recursão é $O(\log_p n)$, o comportamento assintótico total do algoritmo é, portanto, $O(p \log_p n)$.

Implementação

Nesse caso, não precisamos de recursividade, ele pode ser implementado usando iteração.

int factmod(int n, int p) {
    int res = 1;
    while (n > 1) {
        res = (res * ((n/p) % 2 ?  p-1 : 1)) % p;
        for (int i = 2; i <= n%p; ++i)
            res = (res * i) % p;
        n /= p;
    }
    return res % p;
}

Essa implementação funciona em $O(p \log_p n)$.