/****************************************************************************/
/* Encuentra el mcd de n números expresado como combinación lineal de ellos */
/*                                                                          */
/* Jaime Suarez <mcripto@bigfoot.com> 2003                                  */
/* en http://elparaiso.mat.uned.es                                            */
/****************************************************************************/

#include <stdio.h>

#include <stdlib.h>


void mcd(long *a, long *c, long *m, int n);
void mcd_aux(long a, long b, long *alfa, long *beta, long *m);

main(int argc, char *argv[])
{
	long *a, *c, alfa, beta, m;
	int n,i;

	/* Tomar datos de la linea de comandos */
	n=argc-1;
	if (n < 2) {
		printf ("%s n1 n2 ... nk  calcula el mcd de los numeros\n",argv[0]);
		printf ("y lo expresa como combinación lineal de ellos.\n");
		return 1;
	}
	a=(long *)malloc(n*sizeof(long));
	c=(long *)malloc(n*sizeof(long));
	if (c==NULL) { printf("No hay suficiente memoria.\n"); return 1;}
	for (i=0; i<n; i++) *(a+i)=atol(argv[i+1]);
	
	/* Llamada a la función */
	mcd(a,c,&m,n);


	/* Escribir resultados */
	putchar('(');
	for (i=0; i<n-1; i++) printf("%ld,",*(a+i));
	printf("%ld) = %ld = ",*(a+n-1),m);
	for (i=0; i<n-1; i++) 
		printf("%s%ld*%ld",(*(c+i)>=0)?" +":" ",*(c+i),*(a+i));
	printf("%s%ld*%ld\n",(*(c+n-1)>=0)?" +":" ",*(c+n-1),*(a+n-1));
	return 0;
}


/* ----------------------------------------------------------------
 * Entrada: a puntero a un array de n long, c idem, 
 *          n numero de enteros, m puntero a long
 * Salida : ninguna
 * Efecto : *m contiene el mcd de a[0],a[1]...a[n]
 *          c[0]...c[n] los coeficientes de la combinación lineal
 *          igual al mcd.
 ------------------------------------------------------------------*/

void mcd(long *a, long *c, long *m, int n)
{
	long i,j,m1,alfa,beta;
	long *b;
	
	/* Hacemos una copia de a en b */
	b=(long *)malloc(n*sizeof(long));
	if (b==NULL) {printf("No hay suficiente memoria.\n"); exit (1);}
	memcpy(b,a,n*sizeof(long));

	
	/* Comienzo del algoritmo */
	*(c+n-1)=1;
	for (i=n-2; i>=0; i--) {
		mcd_aux(*(b+i),*(b+i+1),&alfa,&beta,&m1);
		*(b+i)=m1;
		*(c+i)=alfa;
		for (j=i+1; j<n; j++) *(c+j) *= beta;
	}
	*m = *b;
	return;
}

/* ------------------------------------------------------------------
 * Entrada: a y b enteros long, alfa, beta y m punteros a long
 * Salida : ninguna
 * Efecto : *m contendrá el mcd de a y b
 *          *alfa y *beta los enteros tales que m=alfa*a+beta*b
 --------------------------------------------------------------------*/

void mcd_aux(long a, long b, long *alfa, long *beta, long *m)
{
	long s0,t0,s1,t1,s,t,q,r=1;
	
	if (a<b) return mcd_aux(b,a,beta,alfa,m);
	s0=1; t0=0;
	s1=0; t1=1;
	while (r != 0) {
		q = a/b;
		r = a%b;
		s = s0 - q*s1;
		t = t0 - q*t1;
		s0=s1; t0=t1;
		s1=s ; t1=t ;
		a =b ; b =r ;
	}
	*m=a;
	*alfa=s0;
	*beta=t0;
	return;
}