/********************************************* * Solving a diophantian equation ax+by = c * * (a,b,c,x,y are integer numbers) * * ------------------------------------------ * * Ref.: "Mathématiques en Turbo-Pascal By * * M. Ducamp and A. Reverchon (2), * * Eyrolles, Paris, 1988" [BIBLI 05]. * * ------------------------------------------ * * Sample run: * * * * SOLVING IN Z EQUATION AX + BY = C * * * * A = 3 * * B = -2 * * C = 7 * * * * Solutions are: * * * * X = 1 + 2*K * * Y = -2 + 3*K * * * * C++ version by J-P Moreau * * (www.jpmoreau.fr) * *********************************************/ #include #include #define FALSE 0 #define TRUE 1 float a,b,c,x0,yy0,p,q; //return greatest common divisor of two integer numbers float GCD(float a,float b) { float x,r; a=(float) int(fabs(a)); b=(float) int(fabs(b)); if (a>1e10 || b>1e10) return 1; if (a==0 || b==0) return 1; if (a1e-10); return a; } /********************************************************** * Solving equation ax+by=c, a,b,c,x,y are integer numbers * * ------------------------------------------------------- * * INPUT: a,b,c coefficients of equation * * OUTPUT: solutions are x0+kp and yy0-kq, with k=0,1,2... * * or k=-1,-2,-3... * * The function returns TRUE if solutions exist (that is, * * if the GCD of a,b is also a divisor of c). * **********************************************************/ bool Diophantian(float a, float b, float c, float *x0,float *yy0,float *p,float *q) { float pg,x1,x2,y1,y2; bool found; if (a==0) return FALSE; if (b==0) return FALSE;; pg=GCD(a,b); a=a/pg; b=b/pg; c=c/pg; if (c!=int(c)) return FALSE; // pg must be also a divisor of c x1=0; y2=0; found=FALSE; do { y1=(c-a*x1)/b; if (y1==int(y1)) { *x0=x1; *yy0=y1; found=TRUE; } else { x1=-x1; if (x1>=0) x1=x1+1; x2=(c-b*y2)/a; if (x2==int(x2)) { *x0=x2; *yy0=y2; found=TRUE; } else { y2=-y2; if (y2>=0) y2=y2+1; } } } while (!found); *p=a; *q=b; return TRUE; } void main() { printf("\n SOLVING IN Z EQUATION AX + BY = C\n\n"); printf(" A = "); scanf("%f",&a); printf(" B = "); scanf("%f",&b); printf(" C = "); scanf("%f",&c); printf("\n"); if (Diophantian(a,b,c,&x0,&yy0,&p,&q)) { printf(" Solutions are:\n\n"); printf(" X=%6.0f +%6.0f *K\n",x0,fabs(q)); printf(" Y=%6.0f",yy0); if (p*q>0) printf(" -"); else printf(" +"); printf("%6.0f *K\n\n",fabs(p)); } else printf(" No solutions.\n\n"); printf("\n"); } // end of file diophan.cpp