DWORD GetGcd(DWORD a,DWORD b)
{
if (a < b)
{
DWORD temp = a;
a = b;
b = temp;
}

DWORD c = a;
DWORD d = b;
DWORD test = 0;
while((test = c % d) > 0)
{
c = d;
d = test;
}

return d;
}

DWORD GetXY(DWORD a,DWORD b,DWORD *xy)
{
BOOL isChange = FALSE;

if (a < b)
{
DWORD temp = a;
a = b;
b = temp;
isChange = TRUE;
}


DWORD k,p0=1,p1=0,q0=0,q1=1,temp;
int n = 0;
DWORD c = a;
DWORD d = b;
DWORD test = 0;
while((test = c%d) > 0)
{
n++;
k = c/d;

if (n==1)
{
p1 = k;
q1 = 1;
}
else
{
temp = p1;
p1 = p1*k+p0;
p0 = temp;

temp = q1;
q1 = q1*k+q0;
q0 = temp;
}

c = d;
d = test;
}

if (n%2 == 1)
{
p1 = 0 - p1;
}
else
{
q1 = 0 - q1;
}

if (isChange)
{
temp = p1;
p1 = q1;
q1 = temp;
}

xy[0] = q1;
xy[1] = p1;

return 0;
}

DWORD GetInv(DWORD a,DWORD m)
{
DWORD xy[2];

if(GetGcd(a,m) == 1)
{
GetXY(a,m,xy);
DWORD temp = xy[0] % m;
if(temp < 0)
{
temp += m;
}
return temp;
}
return -1;
}

int main()
{
DWORD A,B,X,Y,M;

M = 0x10001;
B = 0x6907;
Y = 0xACA4;
X = GetInv(B,M);
A = X * Y % M;
printf("\nA = 0x%04X",A);
_getch();

return 0;
}