Extended Euclid.cpp

/*
    Extended Euclid
    UVa - 10104
*/

#include <bits/stdc++.h>

using namespace std;

#define ll long long

ll gcd(ll p,ll q, ll *x, ll *y)
{
     ll x1,y1;
     ll 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);

     *x = y1;
     *y = (x1 - (ll)floor(p/q)*y1);

     return g;
}

int main()
{
    ll a, b;
    while(scanf("%lld %lld", &a, &b) == 2){
        if(a == 0) swap(a, b);
        ll x, y;
        ll g = gcd(a, b, &x, &y);
        printf("%lld %lld %lld\n", x, y, g);
    }
}