SAMPLE QUESTIONS AND ANSWERS 5

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
_______________________________________________________________
Solution :

#include
long d,x,y;

void extend(long a,long b){
long x1;
if(b>a){
x1=a;
a=b;Q
b=x1;
}

if(b==0){
d=a;
x=1;
y=0;
return;
}

extend(b,a%b);
// d=a;
x1=x-(a/b)*y;
x=y;
y=x1;
}

int main(){
long q,w,e;

while(scanf("%ld %ld", &q, &w)==2){
extend(q,w);
if(w>q){
e=x;
x=y;
y=e;
}
printf("%ld %ld %ld\n",x,y,d);
}
return 0;
}