napisałem poniższą funkcję
Kod: Zaznacz cały
int gcdex(int a,int b, int &x,int &y){
int xa = 1, ya = 0, xb = 0, yb=1;
int a0 = a, b0 = b;
int q;
while(a0 != 0 && b0 != 0)
{
if(abs(a0) > abs(b0))
{
q = a0/b0;
a0 %= b0;
xa -= q*xb;
ya -= q*yb;
}
else
{
q = b0/a0;
b0 %= a0;
xb -= q*xa;
yb -= q*ya;
}
}
if(b0 == 0)
{
x = xa;
y = ya;
}
else
{
x = xb;
y = yb;
}
if(a*x+b*y < 0)
{
x = -x;
y = -y;
}
return a*x+b*y;
}
Przeanalizujmy ten kod razem
