e603. 10104 - Euclid Problem
Tags : 數論 輾轉相除法
Accepted rate : 137人/156人 ( 88% ) [非即時]
評分方式:
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 (50%): 1.0s , <1K
公開 測資點#1 (50%): 1.0s , <1K
Hint :
Tags:
數論 輾轉相除法
出處:
UVA [管理者: ig99lp33lp33 (위즈원) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
41845 s10900156@nh ... (ShanC) e603
63 2024-09-01 11:12
26048 h611103 (mochi) e603
extended euclid
886 2021-07-14 11:36