E D R , A S I H C RSS

Euclid Problem

원문보기
----
인기도: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/조현태

쓰레드

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2009-05-27 07:09:19
Processing time 0.0937 sec