數論 - UVA 10104 - Euclid Problem

UVA 10104 - Euclid Problem


問題


從尤拉（Euclid）以來，我們知道對任何正整數A、B，存在整數X、Y使得AX+BY=D。在這裡D是A、B的最大公因數。本問題是給你A、B，請你找出相對應的X、Y、D

* 中文翻譯：Lucky 貓

Input

每組測試資料一列，有2個正整數 A,B（A,B <= 1000000000）。 

Output

每組測試資料輸出X、Y、D。如果有多組X、Y，請輸出 |X| + |Y| 最小那一組。

Sample Input

4 6
17 17

Sample Output

-1 1 2
0 1 17

解法

github


直接用輾轉相除法即可