Chinesischer Restsatz

21

Der chinesische Restsatz besagt, dass wir immer eine Zahl finden können, die alle erforderlichen Reste unter verschiedenen Primzahlen hervorbringt. Ihr Ziel ist es, Code zu schreiben, um eine solche Zahl in Polynomialzeit auszugeben. Kürzester Code gewinnt.

Nehmen wir zum Beispiel an, wir haben die folgenden Einschränkungen ( %stellt Mod dar):

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

Eine Lösung ist n=44. Die erste Bedingung ist erfüllt, weil 44 = 6*7 + 2und so 44hat der Rest, 2wenn geteilt durch 7, und damit 44 % 7 == 2. Die beiden anderen Bedingungen werden ebenfalls erfüllt. Es gibt andere Lösungen wie n=814und n=-341.

Eingang

Eine nicht leere Liste von Paaren (p_i,a_i), wobei jeder Modul p_ieine bestimmte Primzahl und jedes Ziel a_ieine natürliche Zahl im Bereich ist 0 <= a_i < p_i. Sie können Eingaben in beliebiger Form vornehmen. Es muss nicht unbedingt eine Liste von Paaren sein. Sie können nicht davon ausgehen, dass die Eingabe sortiert ist.

Ausgabe

Eine ganze Zahl ist, nso dass n % p_i == a_ifür jeden Indexi . Es muss nicht der kleinste Wert sein und kann auch negativ sein.

Polynomialzeitbeschränkung

Um günstige Lösungen zu verhindern , die nur versuchen n=0, n=1, n=2, und so weiter, muss Ihr Code in polynomialer Zeit in der laufen Länge der Eingabe . Beachten Sie, dass eine Zahl min der Eingabe eine Länge hat Θ(log m), sodass mihre Länge nicht polynomisch ist. Dies bedeutet, dass Sie nicht bis zu meiner Operationszeit zählen oder eine Operationszeit ausführen können m, aber Sie können arithmetische Operationen für die Werte berechnen.

Sie dürfen kein ineffizientes Eingabeformat wie unary verwenden, um dies zu umgehen.

Andere Verbote

Integrierte Funktionen für folgende Aufgaben sind nicht zulässig: Implementieren Sie den chinesischen Restsatz, lösen Sie Gleichungen oder Faktornummern.

Sie können integrierte Funktionen verwenden, um Modifikationen zu finden und modulare Additionen, Subtraktionen, Multiplikationen und Potenzierungen durchzuführen (mit Exponenten für natürliche Zahlen). Sie können nicht anderen integrierten modularen Operationen verwenden, einschließlich der modularen Invers-, Divisions- und Ordnungsfindung.

Testfälle

Diese ergeben die kleinste nicht negative Lösung. Ihre Antwort kann unterschiedlich sein. Es ist wahrscheinlich besser, wenn Sie direkt überprüfen, ob Ihre Ausgabe jede Einschränkung erfüllt.

[(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
xnor
quelle
Warum keine Teilung?
Jimmy23013
@ user23013 Keine modulare Unterteilung, da es sich im Grunde um eine modulare Inverse handelt.
xnor
Zählt die Matrixinversion zum Lösen von Gleichungen?
Fehler
@flawr: Ich denke schon.
Alex A.
@xnor: Was denkst du? Und wie wäre es mit Optimierungsfunktionen?
Fehler

Antworten:

9

Mathematica, 55 51 45

Modular Inverse ist verboten, modulare Exponentiation ist jedoch erlaubt. Nach Fermats kleinem Satz n^(-1) % p == n^(p-2) % p.

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

Beispiel:

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

Nur zum Spaß:

ChineseRemainder@@Reverse@Thread@#&
Alephalpha
quelle
1
Sie können ein Byte sparen, indem Sie die Reihenfolge der Argumente der innersten Funktion vertauschen, sodass Sie sie verwenden können, PowerMod[#2,#-2,#]und ich glaube auch nicht, dass die Funktion benannt werden muss, wodurch sie auf 48 verringert wird.
Martin Ender,
Ja, unbenannte Funktionen sind in Ordnung.
xnor
6

Python 2, 165 101 99 98 85 Bytes

Verwenden Sie Fermats kleinen Satz wie die anderen Antworten. Kümmert sich nicht darum, die Endsumme im modularen Bereich zu halten, da wir nicht an der kleinsten Lösung interessiert sind. Vielen Dank Volatility für das Speichern von 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
Uri Granta
quelle
1
Sie können das Leerzeichen vorher entfernen for.
isaacg
1
x/a*b*pow(x/a,a-2,a)for a,b in lsollte arbeiten.
Volatility
Hervorragender Punkt! Ich habe versucht, die offensichtliche Redundanz dort loszuwerden, habe aber vergessen, dass ich einfach auspacken konnte.
Uri Granta
4

Pyth, 40 37 36 29

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

Verwendet Fermats kleinen Satz, dank Alephalpha. Berechnet nach dieser Formel .

orlp
quelle
3

Ruby, 129

Nun, Genossen, es scheint, dass Ruby-Lösungen länger sein müssen, da die modulare Exponentiation nicht verfügbar ist, ohne die openssl-Bibliothek zu laden und Konvertierungen in OpenSSL :: BN durchzuführen. Trotzdem viel Spaß beim Schreiben:

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)
Atsby
quelle
Sie brauchen nicht die Pars wenn Sie anrufen require, evaloder puts.
Tutleman,
2

Python 2, 61

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

Dies verwendet eine Variation der Produktkonstruktion , die andere Antworten verwenden.

Die Idee ist, die Einschränkungen zu durchlaufen und die Lösung nzu aktualisieren , um die aktuelle Einschränkung zu erfüllen, ohne die vorherigen durcheinander zu bringen. Zu diesem Zweck verfolgen wir das Produkt Pder bisher gesehenen Primzahlen und stellen fest, dass das Hinzufügen eines Vielfachen von Pkeine Auswirkung auf bereits gesehene Primzahlen hat.

Wir müssen uns also nur ändern, num zufrieden zu stellen, n%p == aindem wir das richtige Vielfache von hinzufügen P. Wir lösen nach dem Koeffizienten c:

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

Dies setzt voraus c = (a-n) * P^(-1), dass das Inverse modulo genommen wird p. Wie andere bemerken, kann die Inverse durch Fermats Little Theorem als berechnet werden P^(-1) = pow(P,p-2,p). Also, c = (a-n) * pow(P,p-2,p)und wir aktualisieren ndurch n+= P * (a-n) * pow(P,p-2,p).

xnor
quelle
1

Haskell, 68 100 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]

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

Edit: jetzt mit einer schnellen "Power / Mod" -Funktion. Alte Version (68 Bytes) mit eingebauter Power-Funktion:

f l=sum[l#m^(m-2)`mod`m*n*l#m|(m,n)<-l]
l#m=product(map fst l)`div`m
nimi
quelle
Ich vermute, dass Ihre Implementierung von Power-Mod keine Polynom-Zeit ist, da der Exponent vor dem Mod eine große Zahl erzeugt. Hast du den letzten Testfall ausprobiert?
Xnor
@xnor: Der letzte Testfall hat nach ein paar Sekunden auf meinem 2-GB-Computer nicht mehr genügend Speicher. Ich habe eine schnelle Power / Mod-Funktion hinzugefügt.
Nimi