/****************************************************************************/
/* Resuelve una ecuacion diofantica en n variables:                         */
/* a0*x0+a1*x1+...+an*xn = b donde ai y b son enteros long                  */
/*                                                                          */
/* Ref: Rosen "Elementary number theory and its applications"               */
/*                                                                          */
/* Jaime Suarez <mcripto@bigfoot.com> 2003                                  */
/* en http://elparaiso.mat.uned.es                                            */
/****************************************************************************/

#include <stdio.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, *x, d, b, pr=1;
	int n,i;

	/* Tomar datos de la linea de comandos */
	n=argc-1;
	if (n < 2) {
		printf ("%s a1 a2 ... ak b  resuelve \n",argv[0]);
		printf ("la ecuacion diofantica a1*x1+a2*x2+...+ak*xk= b\n");
		return 1;
	}
	a=(long *)malloc((n-1)*sizeof(long));
	c=(long *)malloc((n-1)*sizeof(long));
	x=(long *)malloc((n-1)*sizeof(long));

	if (x==NULL) { printf("No hay suficiente memoria.\n"); return 1;}
	for (i=0; i<n-1; i++) *(a+i)=atol(argv[i+1]);
	b=atol(argv[n]);
	
	/* Calculo del mcd como combinacion lineal de los ai */
	mcd(a,c,&d,n-1);

	/* Tiene soluciones? */
	if ((float)b/d != b/d) {
		printf("La ecuacion no tiene soluciones enteras.\n");
		return 0;
	}

	/* Escribir las soluciones generales */
	for (i=0; i<n-1; i++) pr *= *(a+i); pr /= d;
	printf("Soluciones de la forma:\n");
	for (i=0; i<n-2; i++) 
		printf("x%d = %ld + %ld.n\n",i,*(c+i)*b/d, pr/ *(a+i) );
	printf("x%d = %ld + %ld.n\n",n-1,*(c+n-2)*b/d, -(n-2)*pr / *(a+n-2));
	printf("donde n es cualquier entero.\n");
	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;
}