Wprowadzenie do tożsamości Bézouta

GCD dwóch liczb całkowitych A, B jest największą liczbą całkowitą dodatnią, która dzieli obie z nich, nie pozostawiając żadnej reszty. Teraz z powodu właściwości Euclida, że ​​każdą liczbę całkowitą N można podzielić przez inną liczbę całkowitą M w następujący sposób:

istnieją pary u, v takie, że możemy napisać:

Ponieważ tych par jest nieskończona ilość, chcielibyśmy znaleźć specjalne. W rzeczywistości istnieją dokładnie (A, B nie będące zerem) dwie takie pary, które satyfikują

na przykład                                    

Wyzwanie

Celem tego wyzwania jest znalezienie (uporządkowanej) pary współczynników (u, v), które spełniają powyższe ograniczenia i gdzie u musi być dodatnia. To zawęża wynik do unikalnej pary.

Wejście

Możemy założyć, że dane wejściowe są dodatnie, również A zawsze będzie większe niż B (A> B).

Wynik

Wyjście naszego programu / funkcji musi być (uporządkowaną) parą określoną w wyzwaniu.

Zasady

Nie wolno używać wbudowanych rozszerzonych algorytmów euklidesowych (np. W Mathematica można używać, GCDale nie wolno)ExtendedGCD - co i tak by się nie udało dla 5,3).

Odpowiedzią może być pełny program (pobieranie danych wejściowych przez STDIN lub podobny i wysyłanie danych wyjściowych przez STDOUT) lub funkcja (zwracanie pary).

Oprócz pary (u, v) nie powinno być żadnych danych wyjściowych, dozwolone są nowe znaki lub spacje. (nawiasy kwadratowe lub przecinki są w porządku)

To jest golf golfowy, wszystkie standardowe luki są zabronione, a program z najmniejszą liczbą bajtów wygrywa.

Przykłady

(A, B) -> (u, v)
(42, 12) -> (1, -3)
(4096, 84) -> (4, -195)
(5, 3) -> (2, -3)
(1155, 405) -> (20, -57)
(37377, 5204) -> (4365, -31351)
(7792, 7743) -> (7585, -7633)
(38884, 2737) -> (1707, -24251)
(6839, 746) -> (561, -5143)
(41908, 7228) -> (1104, -6401)
(27998, 6461) -> (3, -13)
(23780, 177) -> (20, -2687)
(11235813, 112358) -> (8643, -864301)

MATL , 37 40 bajtów

ZdXK2Gw/:1G*1GK/t_w2$:XI2G*!+K=2#fIb)

Wykorzystuje wydanie (9.3.1) , które jest wcześniejsze niż to wyzwanie.

Jest to podejście oparte na brutalnej sile, więc może nie działać w przypadku dużych nakładów.

Wypróbuj online!Kompilator online jest oparty na nowszej wersji, ale daje takie same wyniki.

Wyjaśnienie

Zd            % implicitly input A and B. Compute their GCD. Call that C
XK            % copy C to clipboard K
2Gw/:         % vector [1, 2, ..., B/C]
1G*           % multiply that vector by A
1GK/t_w2$:    % vector [-A/C, -A/C+1 ..., A/C]
XI            % copy to clipboard I
2G*           % multiply that vector by B
!+            % all pairwise sums of elements from those vectors
K=2#f         % find row and column indices of sum that equals C
Ib)           % index second vector with column (indexing first vector with
              % row is not needed, because that vector is of the form [1, 2, ...])

Haskell, 51 bajtów

a#b=[(u,-v)|v<-[1..],u<-[1..v],gcd a b==u*a-v*b]!!0

Przykład użycia: 27998 # 6461-> (3,-13).

Jest to podejście oparte na brutalnej sile, które wyszukuje wszystkie kombinacje ui vsą poprawnymi rozwiązaniami uporządkowanymi przez ui wybiera pierwszą. Zajmuje to trochę czasu |v|.

Python 3, 101 106 bajtów

Edycja: Dodano kilka ulepszeń i poprawek sugerowanych przez Bruce_Forte .

Odpowiedź wykorzystująca rozszerzony algorytm euklidesowy. W niektórych miejscach jest jednak trochę niezgrabny i mam nadzieję, że jeszcze trochę zagram w golfa. Mógłbym przekonwertować na Python 2, aby zapisać bajt na dzieleniu całkowitoliczbowym ( //), ale nie jestem pewien, w jaki sposób %modułowy operator Pythona 2 działa z drugim ujemnym argumentem, ponieważ jest to kluczowe dla prawidłowego wyjścia.

def e(a,b):
 r=b;x=a;s=z=0;t=y=1
 while r:q=x/r;x,r=r,x%r;y,s=s,y-q*s;z,t=t,z-q*t
 return y%(b/x),z%(-a/x)

Nie golfowany:

def e(a, b):
    r = b
    x = a    # becomes gcd(a, b)
    s = 0
    y = 1    # the coefficient of a
    t = 1
    z = 0    # the coefficient of b
    while r:
        q = x / r
        x, r = r, x % r
        y, s = s, y - q * s
        z, t = t, z - q * t
    return y % (b / x), z % (-a / x) # modulus in this way so that y is positive and z is negative

Mathematica, 80 bajtów

f@l_:=Mod@@NestWhile[{Last@#,{1,-Quotient@@(#.l)}.#}&,{{1,0},{0,1}},Last@#.l>0&]

Objaśnienie :

Rozszerzony algorytm Euklidesa jest tutaj, w Neststylu. Metoda, w której współczynniki są przechowywane w tablicach, umożliwia użycie Dot.

Inną możliwą reprezentacją jest po prostu użycie wyrażenia symbolicznego, na przykład u a - v bz {a->19, b->17}. Taka reprezentacja korzysta z funkcji Mathematica i jest interesująca, ale ma znacznie więcej bajtów.

Przypadki testowe :

f[{5, 3}]              (* {2, -3} *)
f[{42, 12}]            (* {1, -3} *)
f[{11235813, 112358}]  (* {8643, -864301} *)

Rubinowy, 83 bajty

Myślę, że istnieje kilka sposobów na dostrojenie i grę w golfa, ale do tej pory mi się podobało. Może następnie wypróbuję rozszerzone rozwiązanie algorytmu euklidesowego.

->x,y{a=b=0;y.downto(0).map{|u|(-x..0).map{|v|a,b=u,v if u*x+v*y==x.gcd(y)}};p a,b}

Jak to działa

Ten kod zaczyna się od pętli u od yzera do 0, z wewnętrzną pętlą vod -xdo 0, wewnątrz której sprawdzamy co ui vczy u*x+v*y == gcd(x, y). Ponieważ po drodze może być wiele dopasowań (wymaga to bardzo wyczerpującego wyszukiwania), zaczynamy od zera, więc gdy otrzymamy ostatnie z wielu dopasowań, to jest to, gdzie |u|i |v|jest najbliżej 0.

def bezout(x,y)
  a=b=0
  y.downto(0).each do |u|
    (-x..0).each do |v|
      if u*x + v*y == x.gcd(y)
        a,b=u,v
      end
    end
  end
  p a,b
end