El teorema del resto chino nos dice que siempre podemos encontrar un número que produzca los restos requeridos bajo diferentes módulos primos. Su objetivo es escribir código para generar dicho número en tiempo polinómico. El código más corto gana.

Por ejemplo, supongamos que se nos dan estas restricciones ( %representa mod):

n % 7  == 2
n % 5  == 4
n % 11 == 0

Una solución es n=44. La primera restricción se satisface porque 44 = 6*7 + 2, y por lo tanto 44tiene resto 2cuando se divide por 7, y por lo tanto 44 % 7 == 2. Las otras dos restricciones también se cumplen. Existen otras soluciones, como n=814y n=-341.

Entrada

Una lista no vacía de pares (p_i,a_i), donde cada módulo p_ies un primo distinto y cada objetivo a_ies un número natural en el rango 0 <= a_i < p_i. Puede tomar la entrada en cualquier forma que sea conveniente; en realidad no tiene que ser una lista de pares. No puede suponer que la entrada está ordenada.

Salida

Un entero ntal que n % p_i == a_ipara cada índice i. No tiene que ser el valor más pequeño, y puede ser negativo.

Restricción de tiempo polinomial

Para evitar soluciones baratas que simplemente intentan n=0, n=1, n=2, y así sucesivamente, el código debe funcionar en tiempo polinómico en la longitud de la entrada . Tenga en cuenta que un número men la entrada tiene longitud Θ(log m), por mlo que no es polinomial en su longitud. Esto significa que no puede contar hasta mo hacer una operación m, pero puede calcular operaciones aritméticas en los valores.

No puede utilizar un formato de entrada ineficiente como unario para evitar esto.

Otras prohibiciones

Los elementos integrados para hacer lo siguiente no están permitidos: Implementar el teorema del resto chino, resolver ecuaciones o números de factores.

Puede usar las funciones integradas para buscar mods y hacer sumas, restas, multiplicaciones y exponenciaciones modulares (con exponente de números naturales). No puede utilizar otras operaciones modulares integradas, como inversa modular, división y búsqueda de órdenes.

Casos de prueba

Estos dan la solución no negativa más pequeña. Tu respuesta puede ser diferente. Probablemente sea mejor si verifica directamente que su salida satisface cada restricción.

[(5, 3)] 
3

[(7, 2), (5, 4), (11, 0)]
44

[(5, 1), (73, 4), (59, 30), (701, 53), (139, 112)]
1770977011

[(982451653, 778102454), (452930477, 133039003)]
68121500720666070

Mathematica, 55 51 45

El inverso modular está prohibido, pero se permite la exponenciación modular. Por el pequeño teorema de Fermat, n^(-1) % p == n^(p-2) % p.

(PowerMod[x=1##&@@#/#,#-2,#]x).#2&@@Thread@#&

Ejemplo:

In[1]:= f = (PowerMod[x=1##&@@#/#,#-2,#]x).#2&@@Thread@#&;

In[2]:= f[{{5, 3}}]

Out[2]= 3

In[3]:= f[{{7, 2}, {5, 4}, {11, 0}}]

Out[3]= 1584

In[4]:= f[{{5, 1}, {73, 4}, {59, 30}, {701, 53}, {139, 112}}]

Out[4]= 142360350966

Solo por diversión:

ChineseRemainder@@Reverse@Thread@#&

Python 2, 165 101 99 98 85 bytes

Usando el pequeño teorema de Fermat como las otras respuestas. No se molesta en mantener la suma final dentro del rango modular, ya que no estamos interesados ​​en la solución más pequeña. Gracias Volatility por guardar 13 bytes.

l=input();x=reduce(lambda a,b:a*b[0],l,1)
print sum(x/a*b*pow(x/a,a-2,a)for a,b in l)

[(5, 3)]
3
[(7, 2), (5, 4), (11, 0)]
1584
[(5, 1), (73, 4), (59, 30), (701, 53), (139, 112)]
142360350966

Pyth, 40 37 36 29

M*G.^G-H2Hsm*edg/u*GhHQ1hdhdQ

Utiliza el pequeño teorema de Fermat, gracias a alephalpha. Calcula usando esta fórmula .

Rubí, 129

Bueno, camaradas, parece que las soluciones de Ruby deben ser más largas porque la exponenciación modular no está disponible sin cargar la biblioteca openssl y hacer conversiones a OpenSSL :: BN. Aún así, me divertí escribiéndolo:

require("openssl")
z=eval(gets)
x=1
z.map{|a,b|x*=a}
s=0
z.map{|a,b|e=a.to_bn;s+=(x/a).to_bn.mod_exp(e-2,e).to_i*b*x/a}
puts(s)

Pitón 2, 61

n=P=1
for p,a in input():n+=P*(a-n)*pow(P,p-2,p);P*=p
print n

Esto emplea una variación de la construcción del producto que utilizan otras respuestas.

La idea es recorrer las restricciones y actualizar la solución npara cumplir con la restricción actual sin estropear las anteriores. Para ello, rastreamos el producto.P de los primos vistos hasta ahora, y observamos que agregar un múltiplo de Pno tiene ningún módulo de efecto sobre ningún primo ya visto.

Entonces, solo necesitamos cambiar npara satisfacer n%p == aagregando el múltiplo correcto de P. Resolvemos el coeficiente c:

(n + P*c) % p == a

Esto requiere que c = (a-n) * P^(-1), donde se toma el módulo inverso p. Como otros señalan, el inverso puede ser calculado por el pequeño teorema de Fermat como P^(-1) = pow(P,p-2,p). Entonces, c = (a-n) * pow(P,p-2,p)y actualizamos npor n+= P * (a-n) * pow(P,p-2,p).

Haskell, 68100 bytes

f l=sum[p#(m-2)*n*p|(m,n)<-l,let a#0=1;a#n=(a#div n 2)^2*a^mod n 2`mod`m;p=product(map fst l)`div`m]

Uso: f [(5,1), (73,4), (59,30), (701,53), (139,112)]-> 142360350966.

Editar: ahora con una función rápida "power / mod". Versión anterior (68 bytes) con función de potencia incorporada:

f l=sum[l#m^(m-2)`mod`m*n*l#m|(m,n)<-l]
l#m=product(map fst l)`div`m