Euclid Problem

원문보기
----
인기도:B(A,B,C), 성공률:보통(낮음,보통,높음), 레벨:1(1~4)

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

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

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

~cpp 
4 6
17 17

~cpp 
-1 1 2
0 1 17