#include <stdio.h>
#include <conio.h>

void extended_euclid(unsigned __int64 x, unsigned __int64 y, __int64 &a, __int64 &b, unsigned __int64 &gcd){

    unsigned __int64 g=1;

    while (((x & 1)==0) && ((y & 1)==0)){
        x=x/2;
        y=y/2;
        g=2*g;
    };

    __int64 u=x;
    __int64 v=y;
    __int64 A=1;
    __int64 B=0;
    __int64 C=0;
    __int64 D=1;


    do{
        while ((u & 1)==0){
            u=u/2;

            if (((A-B) & 1) == 0){
                A=A/2;
                B=B/2;
            } else {
                A=(A+y)/2;
                B=(B-x)/2;
            }
        };

        while ((v & 1)==0){
            v=v/2;

            if (((C-D) & 1) ==0){
                C=C/2;
                D=D/2;
            } else {
                C=(C+y)/2;
                D=(D-x)/2;
            }
        };

        if (u>=v){
            u = u-v;
            A = A-C;
            B =B-D;
        } else {
            v=v-u;
            C=C-A;
            D=D-B;
            };
    }while (u!=0);

    a = C;
    b = D;
    gcd = g*v;
}

void main()
{
    __int64 x = 693;
    __int64 y = 609;
    __int64 a,b;
    unsigned __int64 gcd;

    extended_euclid(x,y,a,b,gcd);
    printf("a = %I64d\n",a);
    printf("b = %I64d\n",b);
    printf("GCD: = %I64u",gcd);
    getch();
}