La tarea es la siguiente. Dado un número entero x
(tal que el x
módulo 100000000003
no es igual a 0
) presentado a su código de la forma que le resulte conveniente, genere otro número entero y < 100000000003
para que (x * y) mod 100000000003 = 1
.
Su código debe demorar menos de 30 minutos en ejecutarse en una máquina de escritorio estándar para cualquier entrada x
tal que |x| < 2^40
.
Casos de prueba
Entrada: 400000001. Salida: 65991902837
Entrada: 4000000001. Salida: 68181818185
Entrada: 2. Salida: 50000000002
Entrada: 50000000002. Salida: 2.
Entrada: 1000000. Salida: 33333300001
Restricciones
No puede usar ninguna biblioteca o funciones integradas que realicen módulos aritméticos (o esta operación inversa). Esto significa que ni siquiera puedes a % b
prescindir de implementarte %
. Sin embargo, puede utilizar todas las demás funciones integradas aritméticas no modulares.
Pregunta similar
Esto es similar a esta pregunta, aunque espero que sea lo suficientemente diferente como para ser de interés.
100000000003
? (pregunto)Respuestas:
Pyth, 24 bytes
Banco de pruebas
Esto utiliza el hecho de que a ^ (p-2) mod p = a ^ -1 mod p.
Primero, vuelvo a implementar manualmente el módulo, para el caso específico del mod 100000000003. Utilizo la fórmula
a mod b = a - (a/b)*b
, donde/
se divide el piso. Genero el módulo con10^11 + 3
, usando el código+3^T11
, luego lo guardoJ
, luego uso esto y la fórmula anterior para calcular b mod 100000000003 con-b*/bJ+3^T11J
. Esta función se define comoy
conL
.A continuación, comienzo con la entrada, luego la llevo a la décima potencia y reduzco el mod 100000000003, y repito esto 11 veces.
y^GT
es el código ejecutado en cada paso, y louy^GT11Q
ejecuta 11 veces comenzando con la entrada.Ahora tengo
Q^(10^11) mod 10^11 + 3
, y quieroQ^(10^11 + 1) mod 10^11 + 3
, así que multiplico por la entrada con*
, lo reduzco mod 100000000003 cony
una última vez, y la salida.fuente
Haskell ,
118113105101 bytesInspirado en esta solución .
-12 de Ørjan Johansen
Pruébalo en línea!
Haskell , 48 bytes
Una reescritura de esta solución . Si bien es lo suficientemente rápido para el vector de prueba, esta solución es demasiado lenta para otras entradas.
Pruébalo en línea!
fuente
g
un operador(e?b)a s|...
(2) Si cambiaa
ys
luego puede hacer que!
un no operador yy
en línea en él. (3) Puedes deshacerte de lo carowhere
con unlast
truco, a costa de duplicarloz
. Pruébalo en línea!|e==0=a
se deshace de esa molesta duplicación.Brachylog , 22 bytes
Pruébalo en línea!
Esto tomó alrededor de 10 minutos
1000000
con una versión ligeramente diferente (y más larga) del código que fue exactamente dos veces más rápido (verificó solo valores positivos enİ
lugar de positivos y negativos). Por lo tanto, esto debería tomar alrededor de 20 minutos para completar esa entrada.Explicación
Simplemente describimos eso
Input × Output - 1 = 100000000003 × an integer
y dejamos que la aritmética de restricciónOutput
nos encuentre.Técnicamente no necesitamos el etiquetado explícito
≜
, sin embargo, si no lo usamos,~×
no verificaremos el casoN = [100000000003,1]
(porque a menudo es inútil), lo que significa que esto será muy lento para la entrada,2
por ejemplo, porque necesitará encontrar el segundo entero más pequeño en lugar del primero.fuente
İ
, por lo que esto sigue siendo bastante lento para grandes productos.Python,
535149585349 bytes-2 bytes gracias a orlp
-2 bytes gracias a officialaimm
-4 bytes gracias a Felipe Nardi Batist
-3 bytes gracias a isaacg
-1 byte gracias a Ørjan Johansen
-2 bytes gracias a Federico Poloni
Pruébalo en línea!
Me tomó ~ 30 minutos resolver esto. Mi solución es comenzar con el primer número que se modificará a 1. Este número es 1. Si es divisible por x, entonces y es ese número dividido por x. Si no, agregue 10000000003 a este número para encontrar el segundo número cuyo mod 1000000003 será igual a 1 y repita.
fuente
421385994
el tiempo de espera.b
solo necesita una vez, ¿por qué no codificarlo?JavaScript (ES6),
153143141 bytesInspirado por esta respuesta de math.stackexchange.com .
Una función recursiva basada en el algoritmo euclidiano.
El módulo se implementa computando:
Debido a que el cociente también es necesario, hacerlo de esa manera tiene sentido.
Casos de prueba
Mostrar fragmento de código
fuente
C ++ 11 (GCC / Clang, Linux),
104102 byteshttps://ideone.com/gp41rW
Sin golf, basado en el teorema de Euler y la exponencia binaria.
fuente
long
ser de al menos 32 bits, por lo que no necesariamente puede mantenerse1e11 + 3
. Es de 32 bits en Windows x86-64.long
Sin embargo, es un tipo de 64 bits en Linux x86-64 (y otros sistemas operativos que usan el SystemV ABI). Por lo tanto, para ser completamente portátil, necesitaría usarlong long
, que tiene una garantía de al menos 64 bits desde C ++ 11 .__int128_t
no parece ser C ++ estándar, parece ser una extensión gcc, sería genial si lo declararas como un lenguaje (C ++ 11 + gcc).Mathematica, 49 bytes
fuente
PHP, 71 bytes
Casos de prueba
fuente
Ruby , 58 bytes
Utiliza la aplicación de Isaac del pequeño teorema de Fermat por ahora, mientras termino de cronometrar la solución de fuerza bruta.
La versión actual de la fuerza bruta, que es de 47 bytes, aunque
podría seres demasiado lento:Pruébalo en línea!
fuente