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 + 2
und so 44
hat der Rest, 2
wenn geteilt durch 7
, und damit 44 % 7 == 2
. Die beiden anderen Bedingungen werden ebenfalls erfüllt. Es gibt andere Lösungen wie n=814
und n=-341
.
Eingang
Eine nicht leere Liste von Paaren (p_i,a_i)
, wobei jeder Modul p_i
eine bestimmte Primzahl und jedes Ziel a_i
eine 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, n
so dass n % p_i == a_i
fü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 m
in der Eingabe eine Länge hat Θ(log m)
, sodass m
ihre Länge nicht polynomisch ist. Dies bedeutet, dass Sie nicht bis zu m
einer 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
Antworten:
Mathematica,
555145Modular Inverse ist verboten, modulare Exponentiation ist jedoch erlaubt. Nach Fermats kleinem Satz
n^(-1) % p == n^(p-2) % p
.Beispiel:
Nur zum Spaß:
quelle
PowerMod[#2,#-2,#]
und ich glaube auch nicht, dass die Funktion benannt werden muss, wodurch sie auf 48 verringert wird.Python 2,
165101999885 BytesVerwenden 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.
quelle
for
.x/a*b*pow(x/a,a-2,a)for a,b in l
sollte arbeiten.Pyth,
40373629Verwendet Fermats kleinen Satz, dank Alephalpha. Berechnet nach dieser Formel .
quelle
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:
quelle
require
,eval
oderputs
.Python 2, 61
Dies verwendet eine Variation der Produktkonstruktion , die andere Antworten verwenden.
Die Idee ist, die Einschränkungen zu durchlaufen und die Lösung
n
zu aktualisieren , um die aktuelle Einschränkung zu erfüllen, ohne die vorherigen durcheinander zu bringen. Zu diesem Zweck verfolgen wir das ProduktP
der bisher gesehenen Primzahlen und stellen fest, dass das Hinzufügen eines Vielfachen vonP
keine Auswirkung auf bereits gesehene Primzahlen hat.Wir müssen uns also nur ändern,
n
um zufrieden zu stellen,n%p == a
indem wir das richtige Vielfache von hinzufügenP
. Wir lösen nach dem Koeffizientenc
:(n + P*c) % p == a
Dies setzt voraus
c = (a-n) * P^(-1)
, dass das Inverse modulo genommen wirdp
. Wie andere bemerken, kann die Inverse durch Fermats Little Theorem als berechnet werdenP^(-1) = pow(P,p-2,p)
. Also,c = (a-n) * pow(P,p-2,p)
und wir aktualisierenn
durchn+= P * (a-n) * pow(P,p-2,p)
.quelle
Haskell,
68100 BytesVerwendung:
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:
quelle