10104 - Euclid Problem

Problem Link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1045

Solution idea : Straight forward extended euclid.

Solution :

#include<bits/stdc++.h>
#define ll long long
using namespace std;


ll int X=-1,Y=-1;

ll int ext_gcd (ll int A,ll int B){
    ll int x2, y2, x1, y1, x, y, r2, r1, q, r;
    x2 = 1; y2 = 0;
    x1 = 0; y1 = 1;
    for (r2 = A, r1 = B; r1 != 0; r2 = r1, r1 = r, x2 = x1, y2 = y1, x1 = x, y1 = y ) {
        q = r2 / r1;
        r = r2 % r1;
        x = x2 - (q * x1);
        y = y2 - (q * y1);
    }
    X = x2;
    Y = y2;

    return r2;
}

int main()
{
    ll int a,b,e;
    while(scanf("%lld%lld",&a,&b)==2)
{
     e=ext_gcd(a,b);
     printf("%lld %lld %lld\n",X,Y,e);
}




}