/****************************************************************************/ /* 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; }