回分類題庫
d301: (1052cp2_ex4) Euclid Problem
出處:UVA Online Judge

Difficulity : 2
Accepted : 55 Times | Submit :311 Times | Clicks : 664
Accepted : 51 Users | Submit : 66 Users | Accepted rate : 77%
Time Limit :10000 ms | Memory Limit : 64000 KBytes
題目加入時間 : 2017-03-20 11:03

Content :

From Euclid it is known that for any positive integers A and B there exist such integers X and Y that AX+BY=D, where D is the greatest common divisor of A and B. The problem is to find for given A and B corresponding XY and D.

Input :

The input will consist of a set of lines with the integer numbers A and B, separated with space (A,B<1000000001).

Output :

For each input line the output line should consist of three integers X, Y and D, separated with space. If there are several such X and Y, you should output that pair for which |X|+|Y| is the minimal (primarily) and X<=Y (secondarily).

Sample Input :

4 6
14 63
17 17

Sample Output :

-1 1 2
-4 1 7
0 1 17

Hint :


  

Author :

UVA Online Judge (管理員:cp2ta)

  Solve it!   Status Forum (0)

C++
C
JAVA
80718. cs1111 (7 ms , 366KB)
80715. cp99303052 (7 ms , 232KB)
80638. sp17104703010 (8 ms , 236KB)
80828. nccucs105703039 (2 ms , 225KB)
80876. nccucs105703009 (3 ms , 220KB)
80845. nccucs105703031 (3 ms , 262KB)
80779. nccucs105703008 (3 ms , 220KB)
80687. nccucs103702024 (3 ms , 221KB)
沒有解題記錄

執行時間會受很多因素影響因此僅供參考,主機等級請看這裡