Divide a cómo encontrar máximo $x$ que $k^x$ $n!$

Question

Dado los números de $k$ $n$ ¿cómo puedo encontrar el máximo $x$ donde: $n! \equiv\ 0 \pmod{k^x}$?

Traté de calcular $n!$ y, a continuación, hacer una búsqueda binaria sobre un rango $[0,1000]$ por ejemplo calcular $k^{500}$ si $n!$ mod $k^{500}$ es mayor que $0$ entonces calcular $k^{250}$ y así sucesivamente pero tengo que calcular cada valor de tiempo de $n!$ (almacenamiento en bigint y cada vez que manipular con ella es un poco ridículo) Y la hora de calcular las $n!$$O(n)$, por lo que muy mal. Hay más rápido, matemáticas solución a este problema? Matemáticas amigos?:) Saludos Chris

Answer 1

% Primer $p$, el más alto poder de $p$ que divide $n!$ es $$f(n,p) = \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \left\lfloor \frac{n}{p^3} \right\rfloor + \dots.$ $

Si $k$ es primo, usted tiene la respuesta. (Usted puede tapar en $k$ en la fórmula anterior en lugar de $p$.)

Otra cosa, que la primera factorización de $k$ ser $k = p_1^{e_1}p_2^{e_2}\dots p_r^{e_r}$. Entonces, el más alto poder de $p_i^{e_i}$divisoria $n!$ es $\displaystyle\left\lfloor\frac{f(n,p_i)}{e_i}\right\rfloor$. El mínimo de esta expresión sobre los $i$ da la respuesta para $k$.

Answer 2

$n!$ De computación es una muy mala idea gran cantidad $n$. Para encontrar al exponente deseado debe desarrollar algo similar a la fórmula de Legendre.

También podría buscar Legendre en el siguiente documento.

Answer 3

Aquí es posible. Si $p$ es primo, el mayor valor de $p$división de $n!$$$\sum_{k=1}^\infty \left\lfloor {n\over p^k}\right\rfloor.$% $ si el número $k$ está considerando es factorable fácilmente en números primos, este resultado podrá adaptar a sus necesidades.