Euclid Problem

题意翻译

多组数据。每组数据给出两个正整数 $A,B$。令 $D = (A,B)$，求出关于 $x,y$ 的方程 $Ax+By=D$ 中 $|x|+|y|$ 最小的整数解。输出 $x,y,D$。 $1 \leq A,B \leq 10^{9}$

题目描述

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1045 [PDF](https://uva.onlinejudge.org/external/101/p10104.pdf) ![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA10104/d8432c5e14a3099ec1d2fa30ad20970c4e2156c9.png)

输入输出格式

输入格式

![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA10104/780aeeffb4d977d102e402afb0fdfc1cb2fa15cf.png)

输出格式

![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA10104/0bb4baddf4288ac74bb6cd2c8e34174c3907213f.png)

输入输出样例

输入样例 #1

4 6
17 17

输出样例 #1

-1 1 2
0 1 17