[http://online-judge.uva.es/p/v101/10104.html 원문보기]
----
인기도:B(A,B,C), 성공률:보통(낮음,보통,높음), 레벨:1(1~4)

=== About [EuclidProblem] ===
유클리드가 밝혀낸 바에 따르면, 임의의 정수 A, B에 대해 A와 B의 최대공약수를 D라고 할 때 AX + BY = D 를 만족하는 정수 X와 Y가 존재한다. A와 B가 주어졌을 때 위 식을 만족시키는 X와 Y, 그리고 A와 B의 최대공약수 D를 구하라.

=== Input ===
한 줄에 두 개씩의 수가 입력되며 두 수는 각각 A와 B다. A와 B는 스페이스로 구분된다. (A, B < 1,000,000,001).

=== Output ===
입력된 각 줄에 대해 각각 스페이스로 구분된 세 개의 정수 X와 Y 그리고 D를 출력한다. 식을 만족하는 X와 Y가 여러 개 있으면, (첫째로) |X| + |Y|가 최소가 되고 (둘째로) X <= Y 인 값을 출력한다.

=== Sample Input ===
{{{~cpp 
4 6
17 17
}}}

=== Sample Output ===
{{{~cpp 
-1 1 2
0 1 17
}}}

=== 풀이 ===
|| 이름 || 언어 || 시간 || 링크 ||
|| 나휘동 || C++ || 40분 + 30분 + 20분 + 25분|| [EuclidProblem/Leonardong] ||
|| [문보창] || C++ || 10분 || [EuclidProblem/문보창] ||
|| 차영권 || C++ || 1시간30분 || [EuclidProblem/차영권] ||
|| 이동현 || C++ || 3시간 || [EuclidProblem/이동현] ||
|| [곽세환] || C++ || 하루종일 || [EuclidProblem/곽세환] ||
|| [조현태] || C || . || [EuclidProblem/조현태] ||

=== 쓰레드 ===
----
[문제분류] [AOI]