le théorème des restes chinois nous dit que nous pouvons toujours trouver un nombre qui produit tous les restes requis sous différents modules premiers. Votre objectif est d'écrire du code pour sortir un tel nombre en temps polynomial. Le code le plus court gagne.

Par exemple, supposons qu'on nous donne ces contraintes ( %représente le mod):

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

Une solution est n=44. La première contrainte est satisfaite parce que 44 = 6*7 + 2, et il en 44est de même pour le reste 2divisé par 7, et donc 44 % 7 == 2. Les deux autres contraintes sont également respectées. Il existe d'autres solutions, telles que n=814et n=-341.

Contribution

Une liste de paires non vide (p_i,a_i), où chaque module p_iest un nombre premier distinct et chaque cible a_iest un nombre naturel dans la plage 0 <= a_i < p_i. Vous pouvez prendre des informations sous la forme qui vous convient; il n'est pas nécessaire que ce soit une liste de paires. Vous ne pouvez pas supposer que l'entrée est triée.

Production

Un entier ntel que n % p_i == a_ipour chaque index i. Il n'est pas nécessaire que cette valeur soit la plus petite et peut être négative.

Restriction temporelle polynomiale

Pour éviter des solutions bon marché qui tentent simplement n=0, n=1, n=2et ainsi de suite, votre code doit être exécuté en temps polynomial dans la longueur de l'entrée . Notez qu'un nombre mdans l'entrée a une longueur Θ(log m), donc mlui-même n'est pas polynomial dans sa longueur. Cela signifie que vous ne pouvez pas compter mou effectuer une opération m, mais vous pouvez calculer des opérations arithmétiques sur les valeurs.

Vous ne pouvez pas utiliser un format d'entrée inefficace comme unaire pour contourner ce problème.

Autres interdictions

Les fonctions intégrées permettant d'effectuer les opérations suivantes ne sont pas autorisées: implémenter le théorème du reste chinois, résoudre des équations ou des nombres de facteurs.

Vous pouvez utiliser des fonctions intégrées pour trouver des mods et effectuer des additions, des soustractions, des multiplications et des exponentiations modulaires (avec un exposant de nombres naturels). Vous ne pouvez pas utiliser d'autres opérations modulaires intégrées, notamment l'inverse modulaire, la division et la recherche d'ordres.

Cas de test

Ceux-ci donnent la plus petite solution non négative. Votre réponse peut être différente. Il est probablement préférable de vérifier directement que votre sortie satisfait à chaque contrainte.

[(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

L'inverse modulaire est interdit, mais l'exponentiation modulaire est autorisée. Par le petit théorème de Fermat, n^(-1) % p == n^(p-2) % p.

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

Exemple:

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

Juste pour le fun:

ChineseRemainder@@Reverse@Thread@#&

Python 2, 165 101 99 98 85 octets

Utiliser le petit théorème de Fermat comme les autres réponses. Ne prend pas la peine de garder la somme finale dans la plage modulaire, car nous ne sommes pas intéressés par la plus petite solution. Merci Volatility pour avoir économisé 13 octets.

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

Utilise le petit théorème de Fermat, grâce à l'alephalphe. Calcule à l'aide de cette formule .

Rubis, 129

Eh bien, camarades, il semble que les solutions Ruby doivent être plus longues car l'exponentiation modulaire n'est pas disponible sans charger la bibliothèque openssl et effectuer des conversions vers OpenSSL :: BN. Je me suis quand même amusé à l'écrire:

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)

Python 2, 61

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

Cela utilise une variation de la construction du produit que d'autres réponses utilisent.

L'idée est de boucler sur les contraintes et de mettre à jour la solution npour respecter la contrainte actuelle sans gâcher les précédentes. Pour ce faire, nous suivons le produit Pdes nombres premiers vus jusqu'à présent, et observons que l'ajout d'un multiple de Pn'a aucun effet modulo aucun nombre premier déjà vu.

Donc, nous devons juste changer n pour satisfaire n%p == aen ajoutant le bon multiple de P. Nous résolvons pour le coefficient c:

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

Cela nécessite que c = (a-n) * P^(-1), où l'inverse est pris modulo p. Comme d'autres le notent, l'inverse peut être calculé par le petit théorème de Fermat comme P^(-1) = pow(P,p-2,p). Donc,c = (a-n) * pow(P,p-2,p) et nous mettons à jour npar n+= P * (a-n) * pow(P,p-2,p).

Haskell, 68 octets

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]

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

Edit: maintenant avec une fonction "power / mod" rapide. Ancienne version (68 octets) avec fonction d'alimentation intégrée:

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