Die Aufgabe ist die folgende. Wenn eine Ganzzahl x
(so dass x
modulo 100000000003
nicht gleich ist 0
) Ihrem Code in einer Weise präsentiert wird, die Sie für zweckmäßig halten, geben Sie eine andere Ganzzahl aus, y < 100000000003
damit (x * y) mod 100000000003 = 1
.
Du Code muss weniger als 30 Minuten dauern , auf einem Standard - Desktop - Rechner läuft jeden Eingang , x
so dass |x| < 2^40
.
Testfälle
Eingabe: 400000001. Ausgabe: 65991902837
Eingabe: 4000000001. Ausgabe: 68181818185
Eingabe: 2. Ausgabe: 50000000002
Eingabe: 50000000002. Ausgabe: 2.
Eingabe: 1000000. Ausgabe: 33333300001
Beschränkungen
Sie dürfen keine Bibliotheken oder eingebauten Funktionen verwenden, die Modulo-Arithmetik (oder diese umgekehrte Operation) ausführen. Dies bedeutet, dass Sie nicht einmal auf die a % b
Implementierung verzichten %
können. Sie können jedoch auch alle anderen nicht-modulo-arithmetischen Funktionen verwenden.
Ähnliche Frage
Dies ähnelt dieser Frage, obwohl sie hoffentlich so unterschiedlich ist, dass sie immer noch von Interesse ist.
100000000003
? (Antworten:
Pyth, 24 Bytes
Testsuite
Dies nutzt die Tatsache, dass a ^ (p-2) mod p = a ^ -1 mod p.
Zuerst implementiere ich das Modul für den speziellen Fall von mod 100000000003 manuell neu. Ich verwende die Formel
a mod b = a - (a/b)*b
, bei der/
es sich um eine Floored Division handelt. Ich generiere den Modul mit10^11 + 3
,+3^T11
speichere ihn dann inJ
und verwende diese und die obige Formel, um b mod 100000000003 mit zu berechnen-b*/bJ+3^T11J
. Diese Funktion ist definiert alsy
mitL
.Als nächstes beginne ich mit der Eingabe, gehe dann zur zehnten Potenz über und reduziere die Mod 100000000003 und wiederhole diese 11 Mal.
y^GT
ist der Code, der in jedem Schritt ausgeführt wird unduy^GT11Q
der ab der Eingabe elf Mal ausgeführt wird.Jetzt habe
Q^(10^11) mod 10^11 + 3
und will ichQ^(10^11 + 1) mod 10^11 + 3
, also multipliziere ich mit der Eingabe*
, reduziere sie mod 100000000003 mity
einem letzten Mal und gebe aus.quelle
Haskell ,
118113105101 BytesInspiriert von dieser Lösung .
-12 von Ørjan Johansen
Probieren Sie es online!
Haskell , 48 Bytes
Ein Umschreiben dieser Lösung . Während diese Lösung für den Testvektor schnell genug ist, ist sie für andere Eingaben zu langsam.
Probieren Sie es online!
quelle
g
einen Operator(e?b)a s|...
(2) Wenn Sie wechselna
unds
dann können Sie machen!
einen nicht -Operator und Inliney
hinein. (3) Sie können das teurewhere
durch einenlast
Trick auf Kosten der Vervielfältigung loswerdenz
. Probieren Sie es online!|e==0=a
wird diese lästige Vervielfältigung los.Brachylog , 22 Bytes
Probieren Sie es online!
1000000
Bei einer etwas anderen (und längeren) Version des Codes, die genau zweimal schneller war (nur positive Werteİ
anstelle von positiven und negativen Werten prüfen), dauerte dies etwa 10 Minuten . Daher sollte es ungefähr 20 Minuten dauern, bis diese Eingabe abgeschlossen ist.Erläuterung
Wir beschreiben das einfach
Input × Output - 1 = 100000000003 × an integer
und lassenOutput
uns von der Beschränkungsarithmetik leiten .Wir brauchen die explizite Beschriftung technisch nicht
≜
, aber wenn wir sie nicht verwenden,~×
wird der Fall nicht überprüftN = [100000000003,1]
(weil sie oft unbrauchbar ist), was bedeutet, dass dies für die Eingabe sehr langsam ist,2
zum Beispiel, weil die zweitkleinste Ganzzahl gefunden werden muss statt der ersten.quelle
İ
, daher ist dies bei großen Produkten immer noch recht langsam.Python,
535149585349 Bytes-2 Bytes dank orlp
-2 Bytes dank officialaimm
-4 Bytes dank Felipe Nardi Batist
-3 Bytes dank isaacg
-1 Bytes dank Ørjan Johansen
-2 Bytes dank Federico Poloni
Probieren Sie es online!
Ich brauchte ungefähr 30 Minuten, um das herauszufinden. Meine Lösung besteht darin, mit der ersten Zahl zu beginnen, die auf 1 geändert wird. Diese Zahl ist 1. Wenn sie durch x teilbar ist, ist y die durch x geteilte Zahl. Wenn nicht, addiere 10000000003 zu dieser Zahl, um die zweite Zahl zu finden, deren Mod 1000000003 gleich 1 ist, und wiederhole sie.
quelle
421385994
die Zeitüberschreitung.b
nur einmal brauchen , warum nicht hardcodieren?JavaScript (ES6),
153143141 ByteInspiriert von dieser Antwort von math.stackexchange.com .
Eine rekursive Funktion, die auf dem euklidischen Algorithmus basiert.
Modulo wird implementiert durch Computing:
Da der Quotient auch benötigt wird, macht es Sinn, dies so zu tun.
Testfälle
Code-Snippet anzeigen
quelle
C ++ 11 (GCC / Clang, Linux),
104 bis102 Bytehttps://ideone.com/gp41rW
Ungolfed, basierend auf Eulers Theorem und binärer Exponentation.
quelle
long
mindestens 32-Bit sein, kann also nicht unbedingt gelten1e11 + 3
. Es ist 32-Bit unter x86-64 Windows.long
ist jedoch ein 64-Bit-Typ für x86-64-Linux (und andere Betriebssysteme, die SystemV ABI verwenden). Um also vollständig portabel zu sein, müssten Sie verwendenlong long
, was seit C ++ 11 garantiert mindestens 64-Bit ist .__int128_t
scheint kein Standard-C ++ zu sein, es scheint eine gcc-Erweiterung zu sein. Es wäre cool, wenn Sie dies als Sprache angeben würden (C ++ 11 + gcc).Mathematica, 49 Bytes
quelle
PHP, 71 Bytes
Testfälle
quelle
Ruby , 58 Bytes
Verwendet vorerst Isaacgs Anwendung von Fermats kleinem Theorem, während ich mit dem Timing der Brute-Force-Lösung fertig bin.
Aktuelle Brute - Force - Version, die 47 Bytes ist , aber
möglicherweiseist zu langsam:Probieren Sie es online!
quelle