Ihre Aufgabe ist es, zwei ganzzahlige Zahlen anzugeben a
und b
die modulare multiplikative Inverse eines Modulo b zu berechnen, falls es existiert.
Das modulare Inverse von a
modulo b
ist eine c
solche Zahl ac ≡ 1 (mod b)
. Diese Zahl ist b
für jedes Paar von a
und eindeutig modulo b
. Es existiert nur, wenn der größte gemeinsame Teiler von a
und b
ist 1
.
Die Wikipedia-Seite für modulare multiplikative Inverse kann konsultiert werden, wenn Sie weitere Informationen zum Thema benötigen.
Ein- und Ausgang
Die Eingabe erfolgt entweder als zwei Ganzzahlen oder als Liste mit zwei Ganzzahlen. Ihr Programm sollte entweder eine einzelne Zahl, die modulare multiplikative Inverse, die sich im Intervall befindet 0 < c < b
, oder einen Wert ausgeben, der angibt, dass es keine Inverse gibt. Der Wert kann ein beliebiger Wert sein, mit Ausnahme einer Zahl im Bereich (0,b)
, und es kann sich auch um eine Ausnahme handeln. Der Wert sollte jedoch für Fälle gleich sein, in denen es keine Inverse gibt.
0 < a < b
kann angenommen werden
Regeln
- Das Programm sollte irgendwann beendet sein und jeden Testfall in weniger als 60 Sekunden lösen
- Es gelten Standardlücken
Testfälle
Testfälle unten sind im Format angegeben, a, b -> output
1, 2 -> 1
3, 6 -> Does not exist
7, 87 -> 25
25, 87 -> 7
2, 91 -> 46
13, 91 -> Does not exist
19, 1212393831 -> 701912218
31, 73714876143 -> 45180085378
3, 73714876143 -> Does not exist
Wertung
Dies ist Codegolf, daher gewinnt der kürzeste Code für jede Sprache.
Dies und das sind ähnliche Fragen, aber beide fragen nach bestimmten Situationen.
quelle
Antworten:
Mathematica, 14 Bytes
Obligatorische Mathematica eingebaut :
Es ist eine Funktion, die zwei Argumente (
a
undb
) akzeptiert und die Umkehrung eines Mods b zurückgibt, falls es existiert. Wenn nicht, wird der Fehler zurückgegebenModularInverse: a is not invertible modulo b.
.quelle
JavaScript (ES6),
79736261 BytesGibt zurück,
false
wenn das Inverse nicht existiert.Es verwendet den erweiterten euklidischen Algorithmus und löst alle Testfälle fast augenblicklich.
Testfälle
Code-Snippet anzeigen
quelle
f(x,y)
wird immer als Funktionsaufruf analysiert, außer wenn dasfunction
Schlüsselwort explizit vorangestellt ist . Eine anonyme Pfeilfunktion hingegen wird als deklariert(x,y)=>something
undf=(x,y)=>something
weist derf
Variablen die Funktion zu .Gelee , 2 Bytes
Probieren Sie es online!
Dies verwendet eine integrierte Funktion für die modulare Inversion und gibt 0 für keine modulare Inversion zurück.
Gelee , 7 Bytes
Probieren Sie es online!
Gibt eine leere Menge (dargestellt als leere Zeichenfolge) ohne modulare Inverse aus. Läuft auf TIO nicht genügend Arbeitsspeicher für die größten Testfälle, sollte aber bei genügend Arbeitsspeicher funktionieren.
Wie es funktioniert
Wenn Sie für größere Testfälle arbeiten möchten, probieren Sie diese (relativ ungolfed) Version aus, die viel Zeit anstatt Speicher benötigt:
Gelee, 9 Bytes
Probieren Sie es online!
Wie es funktioniert
quelle
Python 2 , 34 Bytes
Probieren Sie es online!
Rekursive Funktion , die gibt
True
fürprint f(1,2)
, was ich glaube , akzeptabel zu sein, und Fehler für ungültige Eingaben.Wir versuchen zu findenx in a ⋅ x ≡ 1( modb ) .
Dies kann geschrieben werden alsa ⋅ x - 1 = k ⋅ b , wo k eine ganze Zahl ist.
Nehmenmodein davon ergibt- 1 ≡ k ⋅ b( moda ) . Bewegen des Minus ergibt- k ≤ b ≤ 1( moda ) , wo wir nachk .
Um zu sehen, wie es dem ursprünglichen Szenario ähnelt, lassen Sie uns rekursiv nachk auflösen, indem wir die Funktion mit f ( - b % a , a ) aufrufen.f( - b % a , a ) (funktioniert, weil Python positive Werte für modulo mit einem negativen Argument ).
Das Programm wiederholt solange, bisein zu 1 wird, was nur dann der Fall ist , wenn das Original ein und b miteinander koprimiert sind (dh eine multiplikative Inverse existiert), oder ein durch Division durch 0 verursachter Fehler auftritt.
Dieser Wert vonk kann in der Gleichung a ⋅ x - 1 = k ⋅ b , um x als k ⋅ b + 1ein .
quelle
R + Zahlen , 15 Bytes
kehrt
NA
für diejenigena
ohne inverses mod zurückb
.R-Fiddle zum Ausprobieren!
R , 33 Bytes (nicht konkurrierend)
Dies wird sehr groß scheitern,
b
da es tatsächlich einen Vektor von32*b
Größenbits erzeugt.Probieren Sie es online!
Gibt
integer(0)
(eine leere Liste) für diejenigena
ohne inversen Mod zurückb
.quelle
Mathematica, 18 Bytes
Eingang
quelle
Python 2 ,
514954535149 Bytes-1 Byte dank officialaimm
-1 Byte dank Shaggy
Probieren Sie es online!
Druckt,
0
wenn es keine Lösung gibt.quelle
0
füra=1
undb=2
; Aus den Testfällen sollte es ausgeben1
.2, 1
31,73714876143
.Japt ,
98 BytesNimmt die Eingaben in umgekehrter Reihenfolge vor. Ausgänge
-1
für keine Übereinstimmung. Schaltet aus, wenn die größere Ganzzahl größer wird.Probier es aus
quelle
73714876143,31
scheint in Firefox einen Fehler wegen unzureichendem Arbeitsspeicher zu verursachen (und Chromium zum Absturz zu bringen). Ich denke nicht, dass dies eine gültige Antwort ist.Python 3 + gmpy , 23 Bytes
Ich glaube nicht, dass es in Python kürzer werden kann.
Probieren Sie es online! (funktioniert nicht, wenn Sie kein gmpy installiert haben)
quelle
Python 3 , 49 Bytes
Probieren Sie es online!
Python 3 , 50 Bytes
Probieren Sie es online!
Dies wird ausgelöst,
IndexError: list index out of range
falls es keine modulare multiplikative Inverse gibt, wie dies nach den Regeln zulässig ist.quelle
31,73714876143
60 Sekunden (bei TIO) kein Ergebnis für die Eingabe zurückgegeben .8th , 6 Bytes
Code
Erläuterung
invmod
ist ein 8. Wort, das den Wert der Umkehrung vona
Modulo berechnetb
. Es kehrt zurücknull
bei Überlauf oder anderen Fehlern zurück.Anwendungs- und Testfälle
quelle
Pari / GP , 22 Bytes
Löst einen Fehler aus, wenn keine Inverse vorhanden ist.
Probieren Sie es online!
quelle
J , 28 Bytes
Probieren Sie es online!
Verwendet den Satz von Euler . Gibt 0 zurück, wenn die Inverse nicht existiert.
Erläuterung
quelle
Pyth , 10 Bytes
3 Bytes gespart dank @Jakube .
Probieren Sie es hier aus!
Gibt
-1
ohne multiplikative Inverse zurück.Code-Aufschlüsselung
Pyth ,
1513 BytesLöst eine Ausnahme aus, falls keine multiplikative Inverse existiert.
Probieren Sie es hier aus!
Pyth , 15 Bytes
Dies fügt viele Bytes hinzu, um den Fall zu behandeln, dass keine solche Anzahl existiert. Das Programm kann erheblich verkürzt werden, wenn dieser Fall nicht behandelt werden muss:
Probieren Sie es hier aus!
quelle
KExm%*QdKK1
xm%*szdQQ1
C (gcc) , 115 Bytes
Probieren Sie es online!
Erweiterter euklidischer Algorithmus, rekursive Version
C (gcc) , 119 Bytes
Probieren Sie es online!
Erweiterter euklidischer Algorithmus, iterative Version
quelle
C (GCC) ,
48 110104 BytesProbieren Sie es online!
Dies sollte innerhalb von 60 Sekunden bei allen Eingaben (die in eine lange passen) funktionieren.
Bearbeiten. Ich missbrauche die
n
Variable bereits, daher kann ich auch davon ausgehen, dass gcc die erste Zuweisung vornimmt%rax
.quelle
f(3,1000001)
717 zurückgegeben, was offensichtlich Unsinn ist (die richtige Antwort lautet 333334). Selbst wenn dieser Fehler durch Verwendung eines breiteren Integer-Typs behoben würde, würde dieser Brute-Force-Ansatz für einige der größeren Testfälle, die in der Herausforderung angegeben wurden, mit Sicherheit eine Zeitüberschreitung bedeuten.Python 2 + Sympy, 74 Bytes
Probieren Sie es online!
Entnommen aus dem Jelly-Quellcode.
quelle
Axiom, 45 Bytes
0 für Fehler sonst z mit x * z Mod y = 1 zurück
quelle
Python 2 , 52 Bytes
-3 Bytes dank Herrn Xcoder.
Probieren Sie es online!
Ausgaben
False
ohne Lösung und Fehler werdenb
größer.Embedded TIO
Ich teste gerade iframes in Stack Snippets und sie funktionieren absolut fantastisch.
Code-Snippet anzeigen
quelle
i*a%b
sein0
?(31,73714876143)
.JavaScript (ES6),
42413938 ByteAusgänge
false
für keine Übereinstimmung. Wirft einen Überlauffehler, wenn die zweite Zahl zu groß wird.quelle
Gelee , 27 Bytes
Probieren Sie es online!
Verwendet den Satz von Euler mit modularer Exponentiation. Da Jelly nicht über eine integrierte Funktion zur Durchführung modularer Exponentiation verfügt, musste diese implementiert werden, und es wurden die meisten Bytes benötigt.
quelle
Axiom, 99 Bytes
es benutzt die Funktion h (); h (a, b) gibt 0 zurück, wenn der Fehler [nicht existent invers] ist, andernfalls wird das z zurückgegeben, so dass a * z mod b = 1 Dies wäre auch dann in Ordnung, wenn die Argumente negativ sind ...
Dies wäre die allgemeine egcd () - Funktion, die eine Liste von int zurückgibt (sie können also auch negativ sein).
So benutzt man es
Ich finde die Basis Algo im Internet von https://pastebin.com/A13ybryc
quelle