e603: 10104 - Euclid Problem
Tags : 數論 輾轉相除法
Accepted rate : 44人/52人 ( 85% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-11-01 16:02

Content

從歐幾里得(Euclid)已知對於任何正整數A和B,存在X和Y符合 AX + BY = D。
其中D是A和B的最大公因數,此問題是對於給定的A和B,要找到相對應的X,Y和D。

Input

輸入為多行。
每行有兩個整數A和B (A,B < 1000000001)。

Output

對於每行輸入,輸出三個整數X,Y和D。
如果有多個符合的X和Y,則應輸出 |X| + |Y| 最小的。
如果有多組滿足最小值,則輸出 X ≤ Y 那對。

Sample Input #1
4 6
17 17
Sample Output #1
-1 1 2
0 1 17
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (100%): 1.0s , <1K
Hint :
Tags:
數論 輾轉相除法
出處:
UVA [管理者:
ig99lp33lp33 (위즈원)
]


ID User Problem Subject Hit Post Date
26048
h611103 (mochi)
e603
extended euclid
18 2021-07-14 11:36