[L1] Problem Euklidesa
Języki:
c
cpp
java
pas
Limit czasu: 3.0 s
Limit pamięci: 0 MB
Limit rozmiaru rozwiązania: 100 kB
Problem
Od czasów Euklidesa wiadomo, że dla każdej pary liczb całkowitych dodatnich A i B istnieją takie liczby całkowite X i Y, że AX + BY = D, gdzie D oznacza największy wspólny dzielnik A i B. Problem polega na znalezieniu dla danych A i B liczb X, Y i D.
Wejście
Wejście będzie składać się z kilku wierszy. Każdy z nich zwierać będzie dwie liczby całkowite A i B, oddzielone spacją (A, B <1000000001).
Wyjście
Dla każdego wiersza wejścia wypisz trójkę liczb X, Y i D, rozdzielając je spacjami (gdzie D jest największym wspólnym dzielnikiem A i B oraz spełnione jest równanie AX+BY=D). Jeżeli istnieje kilka par (X,Y) spełniających warunki zadania, należy wypisać parę, dla której |x|+|Y| jest minimalne (przede wszystkim) oraz X<=Y (jeśli istnieje kilka par o minimalnej sumie wartości bezwzględnych).
Przykładowe wejście
Przykładowe wyjście
Zadanie pochodzi z http://uva.onlinejudge.org
Od czasów Euklidesa wiadomo, że dla każdej pary liczb całkowitych dodatnich A i B istnieją takie liczby całkowite X i Y, że AX + BY = D, gdzie D oznacza największy wspólny dzielnik A i B. Problem polega na znalezieniu dla danych A i B liczb X, Y i D.
Wejście
Wejście będzie składać się z kilku wierszy. Każdy z nich zwierać będzie dwie liczby całkowite A i B, oddzielone spacją (A, B <1000000001).
Wyjście
Dla każdego wiersza wejścia wypisz trójkę liczb X, Y i D, rozdzielając je spacjami (gdzie D jest największym wspólnym dzielnikiem A i B oraz spełnione jest równanie AX+BY=D). Jeżeli istnieje kilka par (X,Y) spełniających warunki zadania, należy wypisać parę, dla której |x|+|Y| jest minimalne (przede wszystkim) oraz X<=Y (jeśli istnieje kilka par o minimalnej sumie wartości bezwzględnych).
Przykładowe wejście
4 6
17 17
Przykładowe wyjście
-1 1 2
0 1 17
