Berechnen Sie den inversen Modul

18

Die Aufgabe:

Gibt einen Wert für aus x, wobei a mod x = bfür zwei gegebene Werte a,b.

Annahme

  • aund bwird immer positive ganze Zahlen sein
  • Es wird nicht immer eine Lösung für geben x
  • Wenn mehrere Lösungen vorhanden sind, geben Sie mindestens eine davon aus.
  • Wenn keine Lösungen vorhanden sind, geben Sie nichts oder einen Hinweis darauf aus, dass keine Lösungen vorhanden sind.
  • Built-Ins sind erlaubt (nicht so spaßig wie andere mathematische Ansätze)
  • Ausgaben sind immer ganze Zahlen

Beispiele

A, B >> POSSIBLE OUTPUTS

5, 2 >> 3
9, 4 >> 5
8, 2 >> 3, 6
6, 6 >> 7, (ANY NUMBER > 6)
8, 7 >> NO SOLUTION
2, 4 >> NO SOLUTION
8, 5 >> NO SOLUTION
10,1 >> 3, 9

Dies ist , also gewinnt das niedrigste Byte.

Graviton
quelle
Kann es Fehler geben, wenn keine Lösung gefunden wird?
Uhr klatschen
@ConfusedMr_C Technisch bedeutet das keine Lösung, also ja.
Graviton

Antworten:

11

JavaScript , 28 27 26 24 23 Bytes

a=>b=>(a-=b)?a>b&&a:b+1

Probieren Sie es online!

false zeigt keine Lösung an.

-1 Danke @Arnauld

eush77
quelle
Schön gemacht und schön golfen.
Shaggy
Um es also aufzurufen, müssen Sie der äußeren Funktion einen Namen geben, sagen wir f=..., und dann aufrufen f(8)(3)? Das scheint ein bisschen schummelig? Die normale Art, eine Funktion aufzurufen, wäre f(8,3), was Ihre Funktionsdefinition länger machen würde.
Steve Bennett
3
@SteveBennett Richtig, die Definition ist Currys , das heißt, sie muss so heißen (8)(3), aber es besteht ein Konsens über PPCG, dass dies zulässig ist . Sie müssen ihm jedoch keinen Namen geben.
Eush77
1
@SteveBennett Es ist amüsant, wie Sie denken, 26 gegen -15 ist alles andere als ein klarer Konsens. Viel Glück beim Streiten.
Eush77
1
@SteveBennett wie ist 55 zu 1 ein schwacher Konsens?
Cyoce
6

MATL , 6 Bytes

tQ:\=f

Probieren Sie es online! Oder überprüfen Sie alle Testfälle .

Erläuterung

Betrachten Eingänge 8, 2als Beispiel.

t    % Implicit input. Duplicate                STACK: 8, 8
Q    % Add 1                                    STACK: 8, 9
:    % Range                                    STACK: 8, [1 2 3 4 5 6 7 8 9]
\    % Modulo                                   STACK: [0 0 2 0 3 2 1 0 8]
=    % Implicit input. Equality comparison      STACK: [0 0 1 0 0 1 0 0 0]
f    % Indices of nonzeros. Implicit display    STACK: [3 6]
Luis Mendo
quelle
4

Gelee , 5 Bytes

‘R⁸%i

Gibt das minimal gültige x zurück oder 0, wenn es kein gibt.

Probieren Sie es online!

Dennis
quelle
3

Groovy, 48 Bytes (mit eingebautem):

{a,b->Eval.me(a+"g").modInverse(Eval.me(b+"g"))}

Eval.me(...+"g") - Fügt dem Eingang "g" hinzu und macht ihn zu einer BigInteger.

modInverse(...) - Führt die inverse Modulo-Operation aus.


Java 8, 70 Bytes

{a,b->return BigInteger.valueOf(a).modInverse(BigInteger.valueOf(b));}
Magische Kraken-Urne
quelle
3

R , 33 28 Bytes

pryr::f(match(b,a%%1:(a+1)))

Probieren Sie es online!

-4 Bytes dank Jarko Dubbeldam.

-1 Byte danke an Giuseppe.

Gibt zurück, NAwenn es keine Lösung gibt. TIO hat die Pryr-Bibliothek nicht installiert, daher wird function(a,b)stattdessen der Code unter diesem Link verwendet .

Nitrodon
quelle
pryr::f(which(a%%1:(a+1)==b)) ist 4 Bytes kürzer.
JAD,
Sie können auch ein anderes Byte löschen, indem Sie verwenden match(b,a%%1:(a+1)), das NAfür einen fehlenden Wert zurückgibt .
Giuseppe
1

Jelly , 11 bis 10 Bytes

³%_⁴
r‘ÇÐḟ

Ein vollständiges Programm, das die beiden positiven ganzen Zahlen aund verwendet bund eine Liste der ganzzahligen Lösungen zwischen min(a,b)+1und max(a,b)+1einschließlich ausgibt.

Probieren Sie es online!

Jonathan Allan
quelle
1

Mathematica 36 Bytes

a_±b_:=Select[Range[9a],a~Mod~#==b&]

Eingang:

5 ± 2
9 ± 4
8 ± 2
6 ± 6
8 ± 7
2 ± 4
8 ± 5
10 ± 1

Ausgabe:

{3}
{5}
{3, 6}
{7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, \
25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, \
42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54}
{}
{}
{}
{3, 9}
Kelly Lowder
quelle
Wenn Sie diese erweiterten ASCII-Operatoren in binärer Form verwenden, müssen Sie beim Definieren ein Leerzeichen voranstellen, andernfalls gibt der Parser einen Fehler aus. So müsste es sein a_ ±b_. Aber es ist kürzer zu verwenden Casesstatt Selecteine eine unbenannte Funktion sowieso:Cases[Range[9#],x_/;#~Mod~x==#2]&
Martin Ender
1

Haskell , 33 Bytes

Abstürze mit, code.hs: out of memory (requested ??? bytes)wenn es keine Lösung gibt (Timeout bei TIO vorher):

a!b=[x|x<-[b+1..],mod(a-b)x<1]!!0

Probieren Sie es online!

Vielen Dank an Ørjan Johansen, der einen Fehler entdeckt hat!

ბიმო
quelle
Dies gibt falsche Antworten für die Testfälle , wo bdividieren a.
Ørjan Johansen
1

C # (Mono C # -Compiler) , 57 56 26 Bytes

Port of Rods Python Antwort. Danke an WW für -1 Byte.

Vielen Dank an Kevin Cruijssen für -30 Bytes.

a=>b=>a-b>b?a-b:a==b?a+1:0

Probieren Sie es online!

Epos
quelle
1
Willkommen auf der Seite! Es sieht so aus, als ob Sie das Leerzeichen danach entfernen können return.
Weizen-Assistent
Willkommen bei PPCG! Für nicht rekursive C # -Antworten ist es immer am besten und am kürzesten, eine Lambda-Funktion ( i=>{/*code here*/}) zu verwenden. In diesem Fall kann es jedoch eine aktuelle Lambda-Funktion sein, ein zusätzliches Byte ( a=>b=>{/*code here*/}anstelle von (a,b)=>{/*code here*/}) zu speichern, da Sie über 2 Eingänge verfügen . Sie können auch die Klammern um Ihre If-Checks entfernen. Insgesamt, ohne dass Ihre Funktionalität a=>b=>a-b>b?a-b:a==b?a+1:0
geändert
Auch wenn Sie es noch nicht gesehen haben, können sowohl Tipps zum Golfen in <allen Sprachen> als auch Tipps zum Golfen in C # interessant sein. Genieße deinen Aufenthalt! :)
Kevin Cruijssen
Ich danke Ihnen allen für die Tipps, die ich in Zukunft beim Golfen berücksichtigen werde.
Epicness
0

Mathematica, 28 Bytes

Which[#>2#2,#-#2,#==#2,#+1]&
Alephalpha
quelle
0

PHP> = 7.1, 51 Bytes

for([,$a,$b]=$argv;++$x<2*$a;)$a%$x!=$b?:print$x._;

Online Version

Jörg Hülsermann
quelle
0

Axiom, 147 128 Bytes

g(a:PI,c:PI):Union(List PI,Stream INT)==(a<c=>[];r:=a-c;r=0=>expand((a+1..)::UniversalSegment INT);[b for b in divisors(r)|b>c])

entgolfen und testen

--a%b=c return all possible b
f(a:PI,c:PI):Union(List PI, Stream INT)==
    a<c=>[]
    r:=a-c
    r=0=>expand((a+1..)::UniversalSegment INT)
    [b  for b in divisors(r)|b>c]

(3) -> [[i,j,g(i,j)] for i in [5,9,8,6,8,2,8,10] for j in [2,4,2,6,7,4,5,1]]
   (3)
   [[5,2,[3]], [9,4,[5]], [8,2,[3,6]], [6,6,[7,8,9,10,11,12,13,14,15,16,...]],
    [8,7,[]], [2,4,[]], [8,5,[]], [10,1,[3,9]]]
                                                      Type: List List Any

Dies würde die ganze Lösung finden, auch die unendliche Menge Lösung ...

RosLuP
quelle
0

Pip , 9 Bytes

a%,a+2@?b

Nimmt die beiden Zahlen als Befehlszeilenargumente. Gibt die kleinste Lösung aus oder null, wenn keine Lösung vorhanden ist. Probieren Sie es online!

Erläuterung

           a, b are cmdline args (implicit)
  ,a+2     Range from 0 up to but not including a+2
a%         Take a mod each of those numbers
           (Note that a%0 returns nil; it emits a warning, but only if warnings are turned on)
      @?b  Find the index of the first occurrence of b in this list, or nil if it doesn't occur
           Autoprint (implicit)

Zum Beispiel mit Eingabe von 8und 2:

   a+2   10
  ,      [0 1 2 3 4 5 6 7 8 9]
a%       [() 0 0 2 0 3 2 1 0 8]

Der auf 0 basierende Index des ersten Vorkommens 2in dieser Liste ist 3, was unsere Lösung ist.

DLosc
quelle
0

J , 14 Bytes

(->]){-,~=*1+]

Probieren Sie es online!

Übersetzung von Rods Python 2-Lösung .

Wie es funktioniert

Die seltenen Fälle, in denen ein J-Code direkt in Python übersetzt werden kann.

(->]){-,~=*1+]  <=>  [(a==b)*(1+b),a-b][a-b>b]
         =*1+]        (a==b)*(1+b)
      -,~            [            ,a-b]
     {                                 [     ]
(->])                                   a-b>b
Bubbler
quelle
0

Japt , 13 Bytes

UµV ?U>V©U:ÒV

Probieren Sie es online!

Übersetzung der JS-Lösung von eush77 .

Der Code ist nur (U-=V)?U>V&&U:-~Vbeim Übertragen auf JS, wo Uund Vsind die beiden Eingabewerte.

Bubbler
quelle
0

Japt , 7 Bytes

(Eventuell) Gibt aus, undefinedwenn es keine Lösung gibt.

@%X¥V}a

Probieren Sie es hier aus

Zottelig
quelle
0

ORK , 566 Bytes

When this program starts:
I have a inputter called I
I have a number called a
I have a number called b
I is to read a
I is to read b
I have a mathematician called M
M's first operand is a
M's second operand is b
M is to subtract
I have a number called n
n is M's result
M's first operand is b
M's second operand is n
M is to compare
I have a scribe called W
If M says it's less then W is to write n
If M says it's less then W is to write "\n"
M's second operand is a
M is to compare
If M says it's equal then W is to write a
If M says it's equal then W is to write a

Probieren Sie es online!

O Objekte R K ool. Glücklicherweise musste ich für diese Aufgabe keine (außer den eingebauten) verwenden.

JosiahRyanW
quelle
0

F #, 40 Bytes

let m a b=Seq.find(fun x->a%x=b){1..a+1}

Probieren Sie es online!

Ziemlich einfach. Wirft ein, System.Collections.Generic.KeyNotFoundExceptionwenn keine Lösung gefunden werden kann.

Sie können es auch in ändern Seq.tryFind, wodurch eine zurückgegeben wird int option, Nonewenn keine Lösung gefunden werden kann.

Ciaran_McCarthy
quelle
0

> <> , 21 Bytes

Gleicher Trick wie bei den meisten veröffentlichten Lösungen. Zuerst bereiten wir alle notwendigen Werte auf dem Stack vor und überprüfen dann die Vergleiche.

::r::{-:{)?nr=?!;1+n;

Probieren Sie es online!

PidgeyUsedGust
quelle
0

Flüstert v2 , 128 Bytes

> Input
> Input
>> 1²
>> (3]
>> 1%L
>> L=2
>> Each 5 4
>> Each 6 7
>> L⋅R
>> Each 9 4 8
> {0}
>> {10}
>> 12∖11
>> Output 13

Probieren Sie es online!

Wie es funktioniert

Es ist nicht überraschend, dass es fast identisch mit den meisten anderen Antworten funktioniert: Es wird eine Liste von Zahlen erstellt und jede mit dem Argument auf den inversen Modul überprüft.

Wenn Sie mit der Programmstruktur von Whispers vertraut sind, können Sie jederzeit zur horizontalen Linie springen. Wenn nicht: Whispers arbeitet im Wesentlichen zeilenweise ab der letzten Zeile. Jede Zeile wird als eine von zwei Optionen eingestuft. Entweder ist es eine Nulllinie oder es ist eine Operatorlinie .

>> Input> {0}> {0}{0}> Input

>>>> 1²>> (3]²nn2>> 1²12

Normalerweise funktionieren Operatorzeilen nur mit Zahlen als Referenz. Möglicherweise haben Sie jedoch die Zeilen >> L=2und bemerkt >> L⋅R. Diese beiden Werte Lund Rwerden in Verbindung mit EachAnweisungen verwendet. EachAnweisungen funktionieren, indem zwei oder drei Argumente als numerische Referenzen verwendet werden. Das erste Argument (z. B. 5) ist eine Referenz auf eine Operatorzeile, in der eine Funktion verwendet wird, und die restlichen Argumente sind Arrays. Anschließend iterieren wir die Funktion über das Array, wobei Lund Rin der Funktion die aktuellen Elemente in den Arrays darstellen, über die iteriert wird. Als Beispiel:

EIN=[1,2,3,4]B=[4,3,2,1]f(x,y)=x+y

> [1, 2, 3, 4]
> [4, 3, 2, 1]
>> L+R
>> Each 3 1 2

EachC=[(1,4),(2,3),(3,2),(4,1)]f(x,y)D=[f(1,4),f(2,3),f(3,2),f(4,1)]=[5,5,5,5]

Probieren Sie es online!


Wie dieser Code funktioniert

Wir arbeiten kontraintuitiv mit der Arbeitsweise von Whispers und beginnen mit den ersten beiden Zeilen:

> Input
> Input

xyx2EIN: =[1...x2]

>> 1%L
>> L=2
>> Each 5 4
>> Each 6 7

>> Each 5 4B: =[ich%x|ichEIN]ein%beinb

>> Each 6 7BC: =[(ich%x)=y|ichEIN]

x=5,y=2EIN=[1,2,3,...,23,24,25]B=[0,1,2,1,0,5,5,...,5,5]C=[0,0,1,0,0,...,0,0]

Wir springen dann runter zu

>> L⋅R
>> Each 9 4 8

Each>> L⋅REINCEINCE

Eich={0Cich=0EINichCich=1

0xy0>> {10}{0}

Caird Coinheringaahing
quelle
-1

C #, 53 Bytes (83 mit Funktionsüberschrift)

static int F(int a, int b){
    for(int i=1;i<=a+1;i++){if(a%i==b)return i;}return 0;
}

Probieren Sie es online

Versuchen Sie es zuerst mit Codegolf. Wahrscheinlich nicht die beste Sprache, noch die effizienteste Codierung.

Alex
quelle
5
Entfernen Sie das unnötige Leerzeichen, um etwa 10 oder mehr Bytes zu sparen
Mr. Xcoder