Twoim zadaniem jest podanie dwóch liczb całkowitych ai bobliczenie modularnej multiplikatywnej odwrotności modułu b, jeśli taki istnieje.

Modularna odwrotność amodulo bjest liczbą ctaką, że ac ≡ 1 (mod b). Ten numer jest unikalnym modułem bdla dowolnej pary ai b. Istnieje tylko wtedy, gdy jest największym wspólnym dzielnikiem ai bjest 1.

Strona Wikipedia dla modułowego Liczba odwrotna może być konsultowany, jeśli potrzebujesz więcej informacji na dany temat.

Wejście i wyjście

Dane wejściowe są podawane jako dwie liczby całkowite lub lista dwóch liczb całkowitych. Twój program powinien wypisać albo pojedynczą liczbę, modularną odwrotność multiplikatywną, która znajduje się w przedziale 0 < c < b, lub wartość wskazującą, że nie ma odwrotności. Wartość może być dowolna, z wyjątkiem liczby z zakresu (0,b), i może być również wyjątkiem. Wartość powinna jednak być taka sama dla przypadków, w których nie ma odwrotności.

0 < a < b można założyć

Zasady

• Program powinien zakończyć się w pewnym momencie i powinien rozwiązać każdy przypadek testowy w mniej niż 60 sekund
• Obowiązują standardowe luki

Przypadki testowe

Poniższe przypadki testowe są podane w formacie, 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

Punktacja

To jest kod golfowy, więc wygrywa najkrótszy kod dla każdego języka.

To i to są podobne pytania, ale oba dotyczą konkretnych sytuacji.

Mathematica, 14 bajtów

Obowiązkowy Mathematica wbudowane :

ModularInverse

Jest to funkcja, która pobiera dwa argumenty ( ai b) i zwraca odwrotność mod b, jeśli istnieje. Jeśli nie, zwraca błąd ModularInverse: a is not invertible modulo b..

JavaScript (ES6), 79 73 62 61 bajtów

Zwraca, falsejeśli odwrotność nie istnieje.

Wykorzystuje rozszerzony algorytm euklidesowy i prawie natychmiast rozwiązuje wszystkie przypadki testowe.

f=(a,b,c=!(n=b),d=1)=>a?f(b%a,a,d,c-(b-b%a)/a*d):b<2&&(c+n)%n

Przypadki testowe

f=(a,b,c=!(n=b),d=1)=>a?f(b%a,a,d,c-(b-b%a)/a*d):b<2&&(c+n)%n

console.log(f(1, 2)) // -> 1
console.log(f(3, 6)) // -> Does not exist
console.log(f(7, 87)) // -> 25
console.log(f(25, 87)) // -> 7
console.log(f(2, 91)) // -> 46
console.log(f(13, 91)) // -> Does not exist
console.log(f(19, 1212393831)) // -> 701912218
console.log(f(31, 73714876143)) // -> 45180085378
console.log(f(3, 73714876143)) // -> Does not exist

Galaretka , 2 bajty

æi

Wypróbuj online!

Używa wbudowanego do modułowego odwrotnego i zwraca 0 dla braku modułowego odwrotnego.

Galaretka , 7 bajtów

R×%⁸’¬T

Wypróbuj online!

Wyprowadza pusty zestaw (reprezentowany jako pusty ciąg) przy braku odwrotności modułowej. Skończy się pamięć w TIO dla największych przypadków testowych, ale powinna działać z wystarczającą ilością pamięci.

Jak to działa

R×%⁸’¬T  
R        Generate range of b
 ×       Multiply each by a
  %⁸     Mod each by b
    ’    Decrement (Map 1 to 0 and all else to truthy)
     ¬   Logical NOT
      T  Get the index of the truthy element.

Jeśli chcesz pracować dla większych przypadków testowych, wypróbuj tę (względnie nie golfową) wersję, która wymaga dużo czasu niż pamięci:

Galaretka, 9 bajtów

×⁴%³’¬ø1#

Wypróbuj online!

Jak to działa

×⁴%³’¬ø1#
        #   Get the first
      ø1      one integer
            which meets:
×⁴            When multiplied by a
  %³          And modulo-d by b
    ’         Decrement
     ¬        Is falsy

Python 2 , 34 bajty

f=lambda a,b:a==1or-~b*f(-b%a,a)/a

Wypróbuj online!

Rekurencyjna funkcja, która daje Trueza print f(1,2), które uważam za dopuszczalne, a błędy dla nieprawidłowych danych wejściowych.

$x$$a\cdot x\equiv 1\pmod{b}$

$a\cdot x-1=k\cdot b$$k$

Nabierający $\mod{a}$$-1\equiv k\cdot b\pmod{a}$$-k\cdot b\equiv1\pmod{a}$$k$ .

$k$$f(-b\%a,a)$ (działa, ponieważ Python podaje wartości dodatnie dla modulo z argumentem ujemnym).

$a$$a$$b$

$k$$a\cdot x-1=k\cdot b$$x$$\frac{k\cdot b+1}{a}$

Liczby R + , 15 bajtów

numbers::modinv

zwraca NAdla tych abez modów inwersyjnych b.

R-Fiddle, aby spróbować!

R , 33 bajty (niekonkurujące)

To się nie powiedzie na bardzo dużych b ponieważ faktycznie tworzy wektor 32*bbitów wielkości .

function(a,b)which((1:b*a)%%b==1)

Wypróbuj online!

Zwraca integer(0)(pusta lista) dla tych abez modów inwersyjnych b.

Mathematica, 18 bajtów

PowerMod[#,-1,#2]&

wkład

[31, 73714876143]

Python 2 , 51 49 54 53 51 49 bajtów

^{-1 bajt dzięki oficjalnemu
-1 bajtowi dzięki Kudłaty}

a,b=input()
i=a<2
while(a*i%b-1)*b%a:i+=1
print+i

Wypróbuj online!

Drukuje, 0gdy nie ma rozwiązania.

Japt , 9 8 bajtów

Pobiera dane wejściowe w odwrotnej kolejności. Wyjścia -1dla braku dopasowania. Występuje, gdy większa liczba całkowita staje się większa.

Ç*V%UÃb1

Sprawdź to

• Oszczędność 1 bajtu dzięki ETH wskazując na błędną i bardzo oczywistą przestrzeń.

Python 3 + gmpy , 23 bajty

Nie sądzę, że w Pythonie może być krótszy.

gmpy.invert
import gmpy

Wypróbuj online! (nie będzie działać, jeśli nie masz zainstalowanego Gmaila)

Python 3 , 49 bajtów

lambda a,b:[c for c in range(b)if-~c*a%b==1][0]+1

Wypróbuj online!

Python 3 , 50 bajtów

lambda a,b:[c for c in range(1,b+1)if c*a%b==1][0]

Wypróbuj online!

Wyrzuca to IndexError: list index out of rangew przypadku, gdy nie ma modularnego odwrotności multiplikatywnej, jak dopuszczają to reguły.

8 , 6 bajtów

Kod

invmod

Wyjaśnienie

invmodjest ósmym słowem, które oblicza wartość odwrotności amodulo b. Powracanull w przypadku przepełnienia lub innych błędów.

Przypadki użycia i testowe

ok> 1 2 invmod .
1
ok> 3 6 invmod .
null
ok> 7 87 invmod .
25
ok> 25 87 invmod .
7
ok> 2 91 invmod .
46
ok> 13 91 invmod .
null
ok> 19 1212393831 invmod .
701912218
ok> 31 73714876143 invmod .
45180085378
ok> 3 73714876143 invmod .
null

Pari / GP , 22 bajty

a->b->lift(1/Mod(a,b))

Zgłasza błąd, gdy nie ma odwrotności.

Wypróbuj online!

J , 28 bajtów

4 :'(1=x+.y)*x y&|@^<:5 p:y'

Wypróbuj online!

Wykorzystuje twierdzenie Eulera . Zwraca 0, jeśli odwrotność nie istnieje.

Wyjaśnienie

4 :'(1=x+.y)*x y&|@^<:5 p:y'  Input: a (LHS), b (RHS)
4 :'                       '  Define an explicit dyad - this is to use the special
                              form `m&|@^` to perform modular exponentiation
                          y   Get b
                      5 p:    Euler totient
                    <:        Decrement
             x                Get a
                   ^          Exponentiate
               y&|@             Modulo b
       x+.y                   GCD of a and b
     1=                       Equals 1
            *                 Multiply

Pyth , 10 bajtów

3 bajty zapisane dzięki @Jakube .

xm%*szdQQ1

Wypróbuj tutaj!

Zwroty -1 brak multiplikatywnej odwrotności.

Podział kodu

xm%*szdQQ1      Let Q be the first input.
 m      Q       This maps over [0 ... Q) with a variable d.
   *szd         Now d is multiplied by the evaluated second input.
  %    Q        Now the remained modulo Q is retrieved.
x        1      Then, the first index of 1 is retrieved from that mapping.

Pyth , 15 13 bajtów

KEhfq1%*QTKSK

Zgłasza wyjątek w przypadku, gdy nie istnieje odwrotność multiplikatywna.

Wypróbuj tutaj!

Pyth , 15 bajtów

Iq1iQKEfq1%*QTK

Dodaje to wiele bajtów do obsługi przypadku, w którym taka liczba nie istnieje. Program można znacznie skrócić, jeśli nie będzie trzeba zajmować się tą sprawą:

fq1%*QTK

Wypróbuj tutaj!

C (gcc) , 115 bajtów

#define L long long
L g(L a,L b,L c,L d){return a?g(b%a,a,d-b/a*c,c):b-1?0:d;}L f(L a,L b){return(g(a,b,1,0)+b)%b;}

Wypróbuj online!

Rozszerzony algorytm euklidesowy, wersja rekurencyjna

C (gcc) , 119 bajtów

long long f(a,b,c,d,t,n)long long a,b,c,d,t,n;{for(c=1,d=0,n=b;a;a=t)t=d-b/a*c,d=c,c=t,t=b%a,b=a;return b-1?0:(d+n)%n;}

Wypróbuj online!

Rozszerzony algorytm euklidesowy, wersja iteracyjna

C (gcc) , 48 110 104 bajtów

#define f(a,b)g(a,b,!b,1,b)
long g(a,b,c,d,n)long a,b,c,d,n;{a=a?g(b%a,a,d,c-(b-b%a)/a*d):!--b*(c+n)%n;}

Wypróbuj online!

Powinno to działać ze wszystkimi wejściami (które mieszczą się w długim czasie) w ciągu 60 sekund.

Edytować. Już nadużywam nzmiennej, więc równie dobrze mogę założyć, że gcc umieszcza pierwsze przypisanie %rax.

Python 2 + sympy, 74 bajty

from sympy import*
def f(a,m):i,_,g=numbers.igcdex(a,m);return g==1and i%m

Wypróbuj online!

Taken from Jelly source code.

Axiom, 45 bytes

f(x:PI,y:PI):NNI==(gcd(x,y)=1=>invmod(x,y);0)

0 for error else return z with x*z Mod y =1

Python 2, 52 bytes

-3 bytes thanks to Mr. Xcoder.

f=lambda a,b,i=1:i*a%b==1and i or i<b and f(a,b,i+1)

Try it online!

Outputs False on no solution and errors out as b gets larger.

Embedded TIO

I'm just testing out iframes in Stack Snippets and they work absolutely fantastic.

html,body{height:100%;}iframe{height:100%;width:100%;border:none;}

<iframe src="https://tio.run/##PY3BCsIwEETv/Yq5CEndy6ZotbhfIh4SanBB09Lm4tdHU8HTvIHhzfzOjym5UqI8/SuMHp4CqfCgrd8FEfZphGJaoJeAWqLZJnu2Jd/XvEJwNUxwlmA6wrFmTzj1FdzhT4QzV@DuR7emidULTdhMA@ZFU/4@tGrLBw"></iframe>

JavaScript (ES6), 42 41 39 38 bytes

Outputs false for no match. Will throw a overflow error as the second number gets to be too large.

x=>y=>(g=z=>x*z%y==1?z:z<y&&g(++z))(1)

Jelly, 27 bytes

²%³
⁴Ç⁹Сx⁸
ÆṪ’BṚçL$P%³×gỊ¥

Try it online!

Uses Euler's theorem with modular exponentiation. Since Jelly doesn't have a builtin to perform modular exponentiation, it had to be implemented, and it took most of the bytes.

Axiom, 99 bytes

w(a,b,x,u)==(a=0=>(b*b=1=>b*x;0);w(b rem a,a,u,x-u*(b quo a)));h(a,b)==(b=0=>0;(b+w(a,b,0,1))rem b)

it use the function h(); h(a,b) return 0 if error [not exist inverse] otherwise it return the z such that a*z mod b = 1 This would be ok even if arguments are negative...

this would be the general egcd() function that retunr a list of int (so they can be negative too)

egcd(aa:INT,bb:INT):List INT==
   x:=u:=-1   -- because the type is INT
   (a,b,x,u):=(aa,bb,0,1)
   repeat
      a=0=>break
      (q,r):=(b quo a, b rem a)
      (b,a,x,u):=(a,r,u,x-u*q)
   [b,x, (b-x*aa)quo bb]

this is how use it

(7) -> h(31,73714876143)
   (7)  45180085378
                                                    Type: PositiveInteger

i find the base algo in internet from https://pastebin.com/A13ybryc