Pyth, 92 bajty
I!%vzhK%2u?sm,ed-hd*ed/F<G2cG2@G1G+~Q,hQ_eQj9 2)J*L/vzhKtKeoSNm-VJ/RhK_*LdQsm+LdtM3/V*LhK_JQ
To całkiem potwór.
Wypróbuj online: demonstracja . Format wejściowy to, c\n[a,b]a format wyjściowy to [x,y].
W przypadku, gdy nie istnieje żadne rozwiązanie liczb całkowitych, nic nie wydrukuję, aw przypadku, gdy nie istnieje naturalne rozwiązanie liczb całkowitych, po prostu wydrukuję losowe rozwiązanie liczb całkowitych.
Wyjaśnienie (zgrubny przegląd)
Najpierw znajdę całkowite rozwiązanie równania ax + by = gcd(a,b)za pomocą algorytmu Extended Euclidean.
Następnie zmodyfikuję rozwiązanie (moje mnożenie ai bprzez c/gcd(a,b)), aby uzyskać całkowite rozwiązanie ax + by = c. Działa to, jeśli c/gcd(a,b)jest liczbą całkowitą. W przeciwnym razie nie ma rozwiązania.
Wszystkie inne rozwiązania całkowite mają postać a(x+n*b/d) + b(y-n*a/d) = c z d = gcd(a,b)do liczby całkowitej n. Używając dwóch nierówności x+n*b/d >= 0i y-n*a/d >= 0mogę określić 6 możliwych wartości dla n. Spróbuję wszystkich 6 z nich i wydrukuję rozwiązanie o najwyższym najniższym współczynniku.
Objaśnienie (szczegółowe)
Pierwszym krokiem jest znalezienie rozwiązania liczby całkowitej w równaniu ax' + by' = gcd(a,b). Można tego dokonać za pomocą rozszerzonego algorytmu euklidesowego. Możesz dowiedzieć się, jak to działa na Wikipedii . Jedyna różnica polega na tym, że zamiast 3 kolumn ( r_i s_i t_i) użyję 6 kolumn ( r_i-1 r_i s_i-1 s_i t_i-1 t_i). W ten sposób nie muszę przechowywać ostatnich dwóch wierszy w pamięci, tylko ostatni.
K%2u?sm,ed-hd*ed/F<G2cG2@G1G+~Q,hQ_eQj9 2) implicit: Q = [a,b] (from input)
j9 2 convert 9 to base 2: [1,0,0,1]
+ Q add to Q => [a,b,1,0,0,1]
this is the initial row
u ) start with G = ^ and update G repeatedly
by the following expression, until
the value of G doesn't change anymore
? @G1 if G[1] != 0:
cG2 split G into parts of 2
m map the parts d to:
, the pair
ed d[1]
-hd*ed/F<G2 d[0]-d[1]*G[0]/G[1]
s unfold
else:
G G (don't change it, stop criterion for u)
%2 take every second element
we get the list [gcd(a,b),x',y']
K store this list in K
~Q,hQ_eQ afterwards change Q to [Q[0],-Q[1]] = [a,-b]
This will be important for the other parts.
Teraz chcę znaleźć rozwiązanie ax + by = c. Jest to możliwe tylko wtedy, gdy c mod gcd(a,b) == 0. Jeżeli równanie to jest spełnione, po prostu mnożąc x',y'się c/gcd(a,b).
I!%vzhK...J*L/vzhKtK implicit: z = c in string format (from input)
%vzhK evaluated(z) mod K[0] (=gcd(a,b))
I! if not ^ than:
/vzhK c/K[0]
*L tK multipy ^ to each element in K[1:] (=[x',y'])
J and store the result in J, this is now [x,y]
Mamy rozwiązanie dla liczb całkowitych ax + by = c. Zauważmy, że x, yalbo oba mogą być ujemne. Naszym celem jest więc przekształcenie ich w nieujemne.
Zaletą równań diofantycznych jest to, że możemy opisać wszystkie rozwiązania za pomocą tylko jednego początkowego rozwiązania. Jeśli (x,y)to rozwiązanie, że wszelkie inne rozwiązania są formy (x-n*b/gcd(a,b),y+n*a/gcd(a,b))do nliczby całkowitej.
Dlatego chcemy znaleźć n, gdzie x-n*b/gcd(a,b) >= 0i y+n*a/gcd(a,b >= 0. Po pewnej transformacji powstają dwie nierówności n >= -x*gcd(a,b)/bi n >= y*gcd(a,b)/a. Zauważ, że symbol nierówności może patrzeć w innym kierunku z powodu podziału z potencjalnym ujemnym alub b. Nie dbam o to tak bardzo, po prostu mówię, że jedna liczba -x*gcd(a,b)/b - 1, -x*gcd(a,b)/b, -x*gcd(a,b)/b + 1zdecydowanie spełnia nierówność 1, a jedna liczba y*gcd(a,b)/a - 1, y*gcd(a,b)/a, y*gcd(a,b)/a + 1spełnia nierówność 2. Jest taka n, która zaspokaja obie nierówności, jedna z 6 liczb również.
Następnie obliczam nowe rozwiązania (x-n*b/gcd(a,b),y+n*a/gcd(a,b))dla wszystkich 6 możliwych wartości n. I drukuję rozwiązanie o najwyższej najniższej wartości.
eoSNm-VJ/RhK_*LdQsm+LdtM3/V*LhK_JQ
_J reverse J => [y,x]
*LhK multiply each value with K[0] => [y*gcd,x*gcd]
/V Q vectorized division => [y*gcd/a,-x*gcd/b]
m map each d of ^ to:
tM3 [-1,0,1]
+Ld add d to each ^
s unfold
these are the possible values for n
m map each d (actually n) of ^ to:
*LdQ multiply d to Q => [a*n,-b*n]
_ reverse => [-b*n,a*n]
/RhK divide by K[0] => [-b*n/gcd,a*n/gcd]
-VJ vectorized subtraction with J
=> [x+b*n/gcd,y-a*n/gcd]
oSN order the solutions by their sorted order
e print the last one
Sortowanie według sortowanej kolejności działa w następujący sposób. Korzystam z tego przykładu2x + 3y = 11
Sortuję każde z 6 rozwiązań (nazywane to kluczami), a oryginalne rozwiązania sortuję według kluczy:
solutions: [1, 3], [4, 1], [7, -1], [-5, 7], [-2, 5], [1, 3]
keys: [1, 3], [1, 4], [-1, 7], [-5, 7], [-2, 5], [1, 3]
sort by key:
solutions: [-5, 7], [-2, 5], [7, -1], [1, 3], [1, 3], [4, 1]
keys: [-5, 7], [-2, 5], [-1, 7], [1, 3], [1, 3], [1, 4]
To sortuje kompletne nieujemne rozwiązanie do końca (jeśli istnieje).