¿Cómo podemos calcular el valor de $\mathrm{gcd}(2^n-1,n!)$ eficiente donde $n$ es muy grande? Yo no podía pensar en cualquier método rápido y eficaz.
Respuestas
¿Demasiados anuncios?
Vincent
Puntos
5027
Aquí es lo que yo haría:
Inicializar un entero grande $N = 2^n - 1$. (Esto requiere 1 o 2 kb.)
Para cada uno de los prime $p \le n$, calcula el $2^n$ mod $p$ = $2^{n \mod (p-1)}$ mod $p$, utilizando un cuadrado y multiplicar algoritmo (ver este artículo de la Wikipedia para más detalles). Si el resultado es $1$, $N$ es divisible por $p$, y queremos que el mayor poder de $p$ que divide tanto a a $N$ $n!$
El mayor poder de $p$ que divide $n!$ es sólo $a = \sum_{r=1}^K \lfloor \frac{n}{p^r}\rfloor$ donde $K$ es cualquier número entero tal que $p^K>n$ (ver, por ejemplo, en este artículo). Así que trate de dividir a la $N$ $p$ $a$ veces, parando si el resto es distinto de cero. El número de veces que este éxito es el poder que queremos.
Ahora sólo se multiplican entre sí todos estos primos poderes.
Tenga en cuenta que $N$ se hace más pequeño y más pequeño a medida que el cálculo de ingresos, limitando la cantidad de la aritmética necesaria. Podría ser más rápido el proceso de los números primos en orden inverso, para acelerar esta tendencia; la experimentación dirá.
gabr
Puntos
20458
Una manera cruda los usos de Fermat poco teorema. $2^{p-1} \equiv 1 \mod p$ , de modo que $p$ divide $2^p - 1$ sólo al $p-1$ divide $n$. Para general enteros $m$, Fermat poco teorema dice $2^{\phi(m)} - 1 \equiv 0 \mod m$ donde $\phi(\cdot)$ es la phi de Euler de la función. Así que tal vez el problema se reduce a encontrar $m$ tal que $\phi(m)$ divide $n$.
