Berechnen Sie die Inverse eines Integer-Moduls 100000000003

21

Die Aufgabe ist die folgende. Wenn eine Ganzzahl x(so dass xmodulo 100000000003nicht 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 < 100000000003damit (x * y) mod 100000000003 = 1.

Du Code muss weniger als 30 Minuten dauern , auf einem Standard - Desktop - Rechner läuft jeden Eingang , xso 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 % bImplementierung 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.

isaacg
quelle
Also ist a- (a / b) * b in Ordnung?
user253751
@immibis Das sieht gut aus.
Tag: Code eingeschränkt?
Felipe Nardi Batista
1
Was ist das Besondere an 100000000003? (
Ich
1
@Lembik Könnten Sie in diesem Fall die Anforderung erwähnen, dass y <100000000003 in der Frage ist?
Isaacg

Antworten:

16

Pyth, 24 Bytes

L-b*/bJ+3^T11Jy*uy^GT11Q

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 mit 10^11 + 3, +3^T11speichere ihn dann in Jund verwende diese und die obige Formel, um b mod 100000000003 mit zu berechnen -b*/bJ+3^T11J. Diese Funktion ist definiert als ymit L.

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^GTist der Code, der in jedem Schritt ausgeführt wird und uy^GT11Qder ab der Eingabe elf Mal ausgeführt wird.

Jetzt habe Q^(10^11) mod 10^11 + 3und will ich Q^(10^11 + 1) mod 10^11 + 3, also multipliziere ich mit der Eingabe *, reduziere sie mod 100000000003 mit yeinem letzten Mal und gebe aus.

isaacg
quelle
Tatsächlich sehr nett!
Ich vermute, es ist zu spät für mich, die Testfälle zu verschärfen ....
1
@Lembik Ich würde es sowieso tun, aber die Meinungen können variieren. Es ist Ihre Herausforderung, damit es so funktioniert, wie Sie es möchten.
Isaacg
So wie die Frage geschrieben ist, ist es möglich, dass Sie die endgültige Kürzung fallen lassen, obwohl ich um eine Klarstellung gebeten habe, ob ein Ergebnis <100000000003 erforderlich ist.
Ørjan Johansen
9

Haskell , 118 113 105 101 Bytes

Inspiriert von dieser Lösung .

-12 von Ørjan Johansen

p=10^11+3
k b=((p-2)?b)b 1
r x=x-div x p*p
(e?b)s a|e==0=a|1<2=(div e 2?b$r$s*s)$last$a:[r$a*s|odd e]

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.

s x=until(\t->t-t`div`x*x==0)(+(10^11+3))1`div`x

Probieren Sie es online!

Bartavelle
quelle
Genial! Ich mag die Potenzierung durch Quadratur.
Isaacg
Die kürzeste Lösung wäre so etwas wie Online ausprobieren! aber ich denke nicht, dass seine Leistung akzeptabel ist ...
Bartavelle
(1) Es ist kürzer zu machen geinen Operator (e?b)a s|...(2) Wenn Sie wechseln aund sdann können Sie machen !einen nicht -Operator und Inline yhinein. (3) Sie können das teure wheredurch einen lastTrick auf Kosten der Vervielfältigung loswerden z. Probieren Sie es online!
Ørjan Johansen
Nun das sind schöne Tricks!
Bartavelle
Oh, und |e==0=awird diese lästige Vervielfältigung los.
Ørjan Johansen
6

Brachylog , 22 Bytes

∧10^₁₁+₃;İ≜N&;.×-₁~×N∧

Probieren Sie es online!

1000000Bei 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 integerund lassen Outputuns von der Beschränkungsarithmetik leiten .

∧10^₁₁+₃                   100000000003
        ;İ≜N               N = [100000000003, an integer (0, then 1, then -1, then 2, etc.)]
            &;.×           Input × Output…
                -₁         … - 1…
                  ~×N∧     … = the product of the elements of N

Wir brauchen die explizite Beschriftung technisch nicht , aber wenn wir sie nicht verwenden, wird der Fall nicht überprüft N = [100000000003,1](weil sie oft unbrauchbar ist), was bedeutet, dass dies für die Eingabe sehr langsam ist, 2zum Beispiel, weil die zweitkleinste Ganzzahl gefunden werden muss statt der ersten.

Tödlich
quelle
1
Wow, ich hätte nie erwartet, dass die Beschränkungsarithmetik das schafft. Genial!
Isaacg
1
@isaacg Die Geschwindigkeit ist leider komplett vom Wert von abhängig İ, daher ist dies bei großen Produkten immer noch recht langsam.
Fatalize
Die Frage wurde aktualisiert. Dauert Ihr Code immer weniger als 30 Minuten?
6

Python, 53 51 49 58 53 49 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

x=input()
t=1
while t-t/x*x:t+=3+10**11
print t/x

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.

Zachary Cotton
quelle
Die erste Zahl, die auf 1
geändert
@orlp lol danke. Das hat mir 2 Bytes erspart :)
Zachary Cotton
Interessant, auf TIO ist dies für alle Testfälle schnell, aber ein bisschen zufälliges Tastenschlagen gab mir 421385994die Zeitüberschreitung.
Ørjan Johansen
@ ØrjanJohansen Gutes Sleuthing.
1
Wenn Sie bnur einmal brauchen , warum nicht hardcodieren?
Federico Poloni
5

JavaScript (ES6), 153 143 141 Byte

Inspiriert von dieser Antwort von math.stackexchange.com .

Eine rekursive Funktion, die auf dem euklidischen Algorithmus basiert.

f=(n,d=(F=Math.floor,m=1e11+3,a=1,c=n,b=F(m/n),k=m-b*n,n>1))=>k>1&d?(e=F(c/k),a+=e*b,c-=e*k,f(n,c>1&&(e=F(k/c),k-=e*c,b+=e*a,1))):a+d*(m-a-b)

Modulo wird implementiert durch Computing:

quotient = Math.floor(a / b);
remainder = a - b * quotient;

Da der Quotient auch benötigt wird, macht es Sinn, dies so zu tun.

Testfälle

Arnauld
quelle
Im letzten Fall benötigen Sie nur 64-Bit-Fußböden, damit Sie die anderen durch 0 | x / y ersetzen und die Deklaration entfernen können
Oki
5

C ++ 11 (GCC / Clang, Linux), 104 bis 102 Byte

using T=__int128_t;T m=1e11+3;T f(T a,T r=1,T n=m-2){return n?f(a*a-a*a/m*m,n&1?r*a-r*a/m*m:r,n/2):r;}

https://ideone.com/gp41rW

Ungolfed, basierend auf Eulers Theorem und binärer Exponentation.

using T=__int128_t;
T m=1e11+3;
T f(T a,T r=1,T n=m-2){
    if(n){
        if(n & 1){
            return f(a * a - a * a / m * m, r * a - r * a / m * m, n / 2);
        }
        return f(a * a - a * a / m * m, r, n / 2);
    }
    return r;
}
SteelRaven
quelle
ISO C ++ muss nur longmindestens 32-Bit sein, kann also nicht unbedingt gelten 1e11 + 3. Es ist 32-Bit unter x86-64 Windows. longist 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 verwenden long long, was seit C ++ 11 garantiert mindestens 64-Bit ist .
Peter Cordes
__int128_tscheint 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).
Felix Dombek
3
Dies sollte keine C ++ - Expertenseite sein, ich hatte gehofft, dass niemand etwas davon merkt.
SteelRaven
@PeterCordes Code Golf muss nicht portabel oder gut geformt sein, es muss nur an einer Implementierung gearbeitet werden.
Aschepler
1
@taschepler: Ich weiß, weshalb ich gesagt habe "du würdest brauchen". Ich fand es nützlich, darauf hinzuweisen, auf welcher Plattform es funktionieren würde / nicht funktionieren würde, falls jemand es versuchte und auf Schwierigkeiten stieß.
Peter Cordes
4

Mathematica, 49 Bytes

x/.FindInstance[x#==k(10^11+3)+1,{x,k},Integers]&
J42161217
quelle
Wie lange dauert die Ausführung?
Weniger als 0,001s auf meinem Computer (für den Fall 2 ^ 40-1)
Keyu Gan
2

PHP, 71 Bytes

for(;($r=bcdiv(bcadd(bcmul(++$i,1e11+3),1),$argn,9))!=$o=$r^0;);echo$o;

Testfälle

Jörg Hülsermann
quelle
1

Ruby , 58 Bytes

Verwendet vorerst Isaacgs Anwendung von Fermats kleinem Theorem, während ich mit dem Timing der Brute-Force-Lösung fertig bin.

->n,x=10**11+3{i=n;11.times{i**=10;i-=i/x*x};i*=n;i-i/x*x}

Aktuelle Brute - Force - Version, die 47 Bytes ist , aber möglicherweise ist zu langsam:

->n,x=10**11+3{(1..x).find{|i|i*=n;i-i/x*x==1}}

Probieren Sie es online!

Wert Tinte
quelle