UVa_10104_Euclid_Problem.cpp

Problem Links:

uva10104,

Problem:

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:

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;
}