algoritmo extendido de euclid C++

Question

Tengo un problema con el Algoritmo Extendido de Euclides. (ax + by = gcd (a, b)) Estoy tratando de determinar tanto el GCD como xey. El GCD no es un problema, pero al usar el método de bucle, algo anda mal con x e y. Normalmente, un número aparece como 0 y el otro es un número negativo anormalmente grande. Código sigue:

#include <iostream> 

using namespace std; 

main() 
{ 
    int a,b,q,x,lastx,y,lasty,temp,temp1,temp2,temp3; 
    cout << "Please input a" << endl; 
    cin >> a; 
    cout << "Please input b" << endl; 
    cin >> b; 
    if (b>a) {//we switch them 
     temp=a; a=b; b=temp; 
    } 
    //begin function 
    x=0; 
    y=1; 
    lastx=1; 
    lasty=0; 
    while (b!=0) { 
     q= a/b; 
     temp1= a%b; 
     a=b; 
     b=temp1; 

     temp2=x-q*x; 
     x=lastx-q*x; 
     lastx=temp2; 

     temp3=y-q*y; 
     y=lasty-q*y; 
     lasty=temp3; 
    } 

    cout << "gcd" << a << endl; 
    cout << "x=" << lastx << endl; 
    cout << "y=" << lasty << endl; 
    return 0; 
} 

Answer 1

Dos de sus asignaciones son equivocados que deben ser:

temp2 = x; 
    x=lastx-q*x; 
    lastx = temp2; 

    temp3 = y; 
    y = lasty-q*y; 
    lasty=temp3; 

Ejemplo de salida con las correcciones anteriores:

Please input a 
54 
Please input b 
24 
gcd6 
x=1 
y=-2 

Answer 2

Aunque la pregunta se ha hecho desde hace mucho tiempo atrás, pero la respuesta ayudará a alguien que esté encontrando la implementación de C++ del algoritmo euclidiano extendido.

Aquí es una recursivo C++ aplicación:

int xGCD(int a, int b, int &x, int &y) { 
    if(b == 0) { 
     x = 1; 
     y = 0; 
     return a; 
    } 

    int x1, y1, gcd = xGCD(b, a % b, x1, y1); 
    x = y1; 
    y = x1 - (a/b) * y1; 
    return gcd; 
} 

Ejemplo con código:

#include <iostream> 

int main() 
{ 
    int a = 99, b = 78, x, y, gcd; 

    if(a < b) std::swap(a, b); 

    gcd = xGCD(a, b, x, y); 
    std::cout << "GCD: " << gcd << ", x = " << x << ", y = " << y << std::endl; 

    return 0; 
} 

de entrada:

a = 99, b = 78

Salida:

GCD: 3, x = -11, y = 14