UVa 10104 - Euclid Problem Solution

#include <iostream>
#include <cmath>
long long A,B,x,y;
long long gcd(long long a,long long b,long long &x,long long &y){
    if(a==0){
        x=0,y=1;
        return b;
    }
    long long x1,y1;
    long long hcf=gcd(b%a,a,x1,y1);
    x=y1-(b/a)*x1;
    y=x1;
    return hcf;
}
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    long long A,B;
    while(cin>>A>>B){
        long long d=gcd(A,B,x,y);
        long long X=x,Y=y,sum=abs(x)+abs(y),ax=x,ay=y,tmp;
        x+=B/d;
        y-=A/d;
        tmp=abs(x)+abs(y);
        while(tmp<sum||(tmp==sum&&x<=y)){
            if(tmp==sum){
                if(x<=y){
                    ax=x,ay=y;
                    break;
                }
            }
            sum=tmp;
            ax=x,ay=y;
            x+=B/d;
            y-=A/d;
        }
        x=X-B/d;
        y=Y+A/d;
        tmp=abs(x)+abs(y);
        while(tmp<sum||(tmp==sum&&x<=y)){
            if(tmp==sum){
                if(x<=y){
                    ax=x,ay=y;
                    break;
                }
            }
            sum=tmp;
            ax=x,ay=y;
            x-=B/d;
            y+=A/d;
        }

        cout<<ax<<' '<<ay<<' '<<d<<endl;
    }
}