島嶼渡假↘下殺$4900起6檔好股票放一年賺5成輕忽小中風,當心變殘障台灣設計引領全球 雙鏡...
2012-06-03 07:21:15 人氣(253) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][gcd變形] 10104 - Euclid Problem

0
收藏
0
推薦


 Euclid Problem 

The Problem

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 X, Y and D.

The Input

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

The 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
17 17

Sample Output

-1 1 2
0 1 17



#include <stdio.h>
int gcd(int a, int b) {
int tmp, flag = 0;
int x1 = 1, y1 = 0, x2 = 0, y2 = 1;
while(a%b) {
if(flag) {
x2 -= a/b*x1;
y2 -= a/b*y1;
} else {
x1 -= a/b*x2;
y1 -= a/b*y2;
}
tmp = a, a = b, b = tmp%b;
flag ^= 1;
}
if(flag)
printf("%d %d", x1, y1);
else
printf("%d %d", x2, y2);
printf(" %d\n", b);
return b;
}
int main() {
int A, B;
while(scanf("%d %d", &A, &B) == 2) {
gcd(A, B);
}
return 0;
}

10104Euclid Problem
台長:Morris
人氣(253) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][hash] 11386 - Triples
此分類上一篇:[UVA][最大生成樹] 1234 - RACING

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文