Calcular el inverso de un módulo entero 100000000003

21

La tarea es la siguiente. Dado un número entero x(tal que el xmódulo 100000000003no es igual a 0) presentado a su código de la forma que le resulte conveniente, genere otro número entero y < 100000000003para 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 xtal 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 % bprescindir 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.

isaacg
fuente
Entonces a- (a / b) * b está bien?
user253751
@immibis Eso se ve bien.
etiqueta: código restringido?
Felipe Nardi Batista
1
¿Qué tiene de especial 100000000003? (pregunto)
NoOneIsHere
1
@Lembik En ese caso, ¿podría mencionar el requisito de que y <100000000003 en la pregunta?
isaacg

Respuestas:

16

Pyth, 24 bytes

L-b*/bJ+3^T11Jy*uy^GT11Q

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 con 10^11 + 3, usando el código +3^T11, luego lo guardo J, luego uso esto y la fórmula anterior para calcular b mod 100000000003 con -b*/bJ+3^T11J. Esta función se define como ycon L.

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^GTes el código ejecutado en cada paso, y lo uy^GT11Qejecuta 11 veces comenzando con la entrada.

Ahora tengo Q^(10^11) mod 10^11 + 3, y quiero Q^(10^11 + 1) mod 10^11 + 3, así que multiplico por la entrada con *, lo reduzco mod 100000000003 con yuna última vez, y la salida.

isaacg
fuente
¡Muy bueno de verdad!
Estoy adivinando de que sea demasiado tarde para endurecer los casos de prueba ....
1
@Lembik Lo haría de todos modos, pero las opiniones pueden variar. Es tu desafío, haz que funcione como quieres.
isaacg
Por la forma en que está escrita la pregunta, es posible que pueda eliminar la reducción final, aunque solicité una aclaración si se requiere un resultado <100000000003.
Ørjan Johansen
9

Haskell , 118 113 105 101 bytes

Inspirado en esta solución .

-12 de Ørjan Johansen

p=10^11+3
k b=((p-2)?b)b 1
r x=x-div x p*p
(e?b)s a|e==0=a|1<2=(div e 2?b$r$s*s)$last$a:[r$a*s|odd e]

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.

s x=until(\t->t-t`div`x*x==0)(+(10^11+3))1`div`x

Pruébalo en línea!

bartavelle
fuente
¡Increíble! Me gusta la exponenciación por enfoque cuadrado.
isaacg
La solución más corta sería algo como ¡ Pruébelo en línea! pero no creo que su rendimiento sea aceptable ...
bartavelle
(1) Es más corto hacer gun operador (e?b)a s|...(2) Si cambia ay sluego puede hacer que !un no operador y yen línea en él. (3) Puedes deshacerte de lo caro wherecon un lasttruco, a costa de duplicarlo z. Pruébalo en línea!
Ørjan Johansen
¡Ahora esos son buenos trucos!
bartavelle
Ah, y |e==0=ase deshace de esa molesta duplicación.
Ørjan Johansen
6

Brachylog , 22 bytes

∧10^₁₁+₃;İ≜N&;.×-₁~×N∧

Pruébalo en línea!

Esto tomó alrededor de 10 minutos 1000000con 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 integery dejamos que la aritmética de restricción Outputnos encuentre.

∧10^₁₁+₃                   100000000003
        ;İ≜N               N = [100000000003, an integer (0, then 1, then -1, then 2, etc.)]
            &;.×           Input × Output…
                -₁         … - 1…
                  ~×N∧     … = the product of the elements of N

Técnicamente no necesitamos el etiquetado explícito , sin embargo, si no lo usamos, no verificaremos el caso N = [100000000003,1](porque a menudo es inútil), lo que significa que esto será muy lento para la entrada, 2por ejemplo, porque necesitará encontrar el segundo entero más pequeño en lugar del primero.

Fatalizar
fuente
1
Wow, nunca hubiera esperado que la aritmética de restricciones lo lograra. ¡Increíble!
isaacg
1
@isaacg Desafortunadamente, la velocidad de esto depende completamente del valor de İ, por lo que esto sigue siendo bastante lento para grandes productos.
Fatalize
Se actualizó la pregunta. ¿Su código siempre toma menos de 30 minutos?
6

Python, 53 51 49 58 53 49 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

x=input()
t=1
while t-t/x*x:t+=3+10**11
print t/x

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.

Algodón Zachary
fuente
El primer número que cambiará a 1 es 1 ...
orlp
@orlp lol gracias. Eso me salvó 2 bytes :)
Zachary Cotton
Interesante, en TIO esto es rápido para todos los casos de prueba, pero un golpe de teclado un poco aleatorio me dio 421385994el tiempo de espera.
Ørjan Johansen
@ ØrjanJohansen Buena investigación.
1
Si bsolo necesita una vez, ¿por qué no codificarlo?
Federico Poloni
5

JavaScript (ES6), 153 143 141 bytes

Inspirado por esta respuesta de math.stackexchange.com .

Una función recursiva basada en el algoritmo euclidiano.

f=(n,d=(F=Math.floor,m=1e11+3,a=1,c=n,b=F(m/n),k=m-b*n,n>1))=>k>1&d?(e=F(c/k),a+=e*b,c-=e*k,f(n,c>1&&(e=F(k/c),k-=e*c,b+=e*a,1))):a+d*(m-a-b)

El módulo se implementa computando:

quotient = Math.floor(a / b);
remainder = a - b * quotient;

Debido a que el cociente también es necesario, hacerlo de esa manera tiene sentido.

Casos de prueba

Arnauld
fuente
Solo necesita un piso de 64 bits en la última ocurrencia para que pueda reemplazar los otros con 0 | x / a y eliminar la declaración
Oki
5

C ++ 11 (GCC / Clang, Linux), 104 102 bytes

using T=__int128_t;T m=1e11+3;T f(T a,T r=1,T n=m-2){return n?f(a*a-a*a/m*m,n&1?r*a-r*a/m*m:r,n/2):r;}

https://ideone.com/gp41rW

Sin golf, basado en el teorema de Euler y la exponencia binaria.

using T=__int128_t;
T m=1e11+3;
T f(T a,T r=1,T n=m-2){
    if(n){
        if(n & 1){
            return f(a * a - a * a / m * m, r * a - r * a / m * m, n / 2);
        }
        return f(a * a - a * a / m * m, r, n / 2);
    }
    return r;
}
SteelRaven
fuente
ISO C ++ solo requiere longser de al menos 32 bits, por lo que no necesariamente puede mantenerse 1e11 + 3. Es de 32 bits en Windows x86-64. longSin 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 usar long long, que tiene una garantía de al menos 64 bits desde C ++ 11 .
Peter Cordes
__int128_tno parece ser C ++ estándar, parece ser una extensión gcc, sería genial si lo declararas como un lenguaje (C ++ 11 + gcc).
Felix Dombek
3
Se supone que este no es un sitio de expertos en C ++, espero que nadie lo note.
SteelRaven
@PeterCordes Code golf no necesita ser portátil o estar bien formado, solo necesita trabajar en una implementación.
aschepler
1
@aschepler: Yo sé, por lo que he dicho "que sería necesario". Pensé que era útil señalar en qué plataforma funcionaría / no funcionaría, en caso de que alguien lo intentara y tuviera problemas.
Peter Cordes
4

Mathematica, 49 bytes

x/.FindInstance[x#==k(10^11+3)+1,{x,k},Integers]&
J42161217
fuente
¿Cuánto tiempo lleva esto correr?
Menos de 0.001s en mi computadora (para el caso 2 ^ 40-1)
Keyu Gan
2

PHP, 71 bytes

for(;($r=bcdiv(bcadd(bcmul(++$i,1e11+3),1),$argn,9))!=$o=$r^0;);echo$o;

Casos de prueba

Jörg Hülsermann
fuente
1

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.

->n,x=10**11+3{i=n;11.times{i**=10;i-=i/x*x};i*=n;i-i/x*x}

La versión actual de la fuerza bruta, que es de 47 bytes, aunque podría ser es demasiado lento:

->n,x=10**11+3{(1..x).find{|i|i*=n;i-i/x*x==1}}

Pruébalo en línea!

Tinta de valor
fuente