Encontrando a potência de um divisor fatorial

Você recebe dois números $n$ e $k$. Encontre a maior potência de $k$ $x$ tal que $n!$ é divisível por $k^x$.

Primo $k$

Vamos primeiro considerar o caso do primo $k$. A expressão explícita para um fatorial:

$$n! = 1 \cdot 2 \cdot 3 \ldots (n-1) \cdot n$$

Observe que todo $k$-ésimo elemento do produto é divisível por $k$, ou seja, acrescenta $+1$ para a resposta; o número de tais elementos é $\Bigl\lfloor\dfrac{n}{k}\Bigr\rfloor$.

A seguir, cada $k^2$-ésimo elemento é divisível por $k^2$, ou seja, acrescenta outro $+1$ para a resposta (a primeira potência de $k$ já foi contada no parágrafo anterior). O número de tais elementos é $\Bigl\lfloor\dfrac{n}{k^2}\Bigr\rfloor$.

E assim por diante, para cada $i$ e então cada $k^i$-ésimo elemento acrescenta outro $+1$ para a resposta, e existem $\Bigl\lfloor\dfrac{n}{k^i}\Bigr\rfloor$ tais elementos.

A resposta final será

$$\Bigl\lfloor\dfrac{n}{k}\Bigr\rfloor + \Bigl\lfloor\dfrac{n}{k^2}\Bigr\rfloor + \ldots + \Bigl\lfloor\dfrac{n}{k^i}\Bigr\rfloor + \ldots$$

A soma é obviamente finita, uma vez que apenas aproximadamente os primeiros $\log_k n$ elementos são diferentes de zero. Portanto, o tempo de execução desse algoritmo é $O(\log_k n)$.

Implementação


int fact_pow (int n, int k) { int res = 0; while (n) { n /= k; res += n; } return res; }

Composto $k$

A mesma ideia não pode ser aplicada diretamente. Em vez disso, podemos fatorar $k$, representando-o como $k = k_1^{p_1} \cdot \ldots \cdot k_m^{p_m}$. Para cada $k_i$, encontramos o número de vezes que ele está presente em $n!$ Usando o algoritmo descrito acima - vamos chamar esse valor de $a_i$. A resposta para um $k$ composto será

$$\min_ {i=1 \ldots m} \dfrac{a_i}{p_i}$$