Algoritmo de Euclides Extendido

Es un metodo sistematico que sirve para hallar el mcd de dos numeros enteros
positivos, el cual es expresado como la combinacion lineal de dos numeros enteros
x e y, es decir d = ax + by. (d es el mcd de a y b)

Codigo en C++

El siguiente programa retorna un array con 3 valores : mcd(a,b) , x , y

long* alg_euc_ext(int n1,int n2) // n1 es a y n2 es b
{   
   long array[3],x=0,y=0,d=0,x2 = 1,x1 = 0,y2 = 0,y1 = 1,q = 0, r = 0;
  if(n2==0)
  {
  array[0]=n1;
  array[1]=1; 
  array[2]=0;  
  }
  else
  {
   while(n2>0) 
      {
     q = (n1/n2); 
      r = n1 - q*n2; 
      x = x2-q*x1; 
      y = y2 - q*y1; 
      n1 = n2; 
      n2 = r; 
      x2 = x1; 
      x1 = x; 
      y2 = y1;             
      y1 = y; 
      }
      array[0] = n1;   // mcd (n1,n2)
      array[1] = x2;   // x
      array[2] = y2;   // y
    }
    return array;
}