uva10104,

# 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).

```4 6
17 17```

## Sample Output

```-1 1 2
0 1 17```

## Source Code:

//Mon Apr  4 02:02:17 CDT 2011
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

long gcd(long p, long q, long *x, long *y)
{
long x1, y1;
long g;
if (q > p) return (gcd(q, p, y, x));

if (q == 0)
{
*x = 1;
*y = 0;
return (p);
}

g = gcd(q, p % q, &x1, &y1);

//cout << x1 << "," << y1 << "," << g << endl;
*x = y1;
*y = (x1 - floor(p / q) * y1);

return (g);
}

int main(int argc, char* argv[])
{
//freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
long x, y;
long a, b;
while (cin >> a >> b)
{
long g = gcd(a, b, &x, &y);
cout << x << " " << y << " " << g << endl;
}
//fclose(stdin);
//fclose(stdout);
return 0;
}