/****************************************************************************/
/* Resolucion de ecuaciones diofanticas de la forma ax+by = c               */
/* donde a,b y c son enteros long.                                          */
/*                                                                          */
/* Jaime Suarez <mcripto@bigfoot.com> 2003                                  */
/* en http://elparaiso.mat.uned.es                                            */
/****************************************************************************/

#include <stdio.h>
long mcd(long a,long b,long *alfa,long *beta);

int main()
{
	long a,b,c,d,alfa,beta,x0,y0,n0,n1,tmp,nmin;
	char mayn0=0, mayn1=0;
	
	printf("Resolucion de ecuaciones diofanticas de la forma\n");
	printf(" ax + by = c \n\n");
	printf("Introduzca los coeficientes.\n");
	printf("a= "); scanf("%ld",&a);
	printf("b= "); scanf("%ld",&b);
	printf("c= "); scanf("%ld",&c);
	
	d=mcd(a,b,&alfa,&beta);
	if ((float)c/d != c/d) {
		printf("La ecuacion no tiene soluciones enteras.\n");
		return 0;
	}
	
	/* Una solucion será: */
	x0=alfa*c/d;
	y0=beta*c/d;

	/* Y en general todas son: */
	printf("Las soluciones de %ldx+%ldy=%ld son:\n" ,a,b,c);
	printf("\tx= %ld + %ld .n\n",x0,b/d);
	printf("\ty= %ld + %ld .n\n",y0,-a/d);
	printf("donde n es cualquier número entero.\n");

	/* Soluciones positivas? */
	n0=-x0*d/b;
	n1=y0*d/a;
	if (b/d>0) {n0++; mayn0=1;}
	if (a/d<0) {n1++; mayn1=1;}
	if (n0>n1) 
		{tmp=n0;n0=n1;n1=tmp; tmp=mayn0;mayn0=mayn1;mayn1=tmp;}
	if (mayn0==0 && mayn1==1) 
		{printf("No tiene soluciones positivas.\n");return 0;}
	else if (mayn0==0 && mayn1==0) nmin=n0;
	else if (mayn0==1 && mayn1==1) nmin=n1;
	else nmin=n0;

	printf("Mínima solucion positiva: x=%ld y=%ld (para n=%ld)\n",
			x0+nmin*b/d, y0-nmin*a/d, nmin);
	
	return 0;
}

	

/* ------------------------------------------------------------------
 * Entrada: a y b enteros long, alfa, beta punteros a long
 * Salida : el mcd como entero long
 * Efecto : *alfa y *beta los enteros tales que mcd=alfa*a+beta*b
 --------------------------------------------------------------------*/

long mcd(long a, long b, long *alfa, long *beta )
{
	long s0,t0,s1,t1,s,t,q,r=1;
	
	if (a<b) return mcd(b,a,beta,alfa);
	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 ;
	}
	*alfa=s0;
	*beta=t0;
	return a;
}