/*********************************************
* 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 <stdio.h>
#include <math.h>

#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 (a<b) {
    x=a; a=b; b=x;
  }
  do {
    r=a-b*int(a/b);
    a=b; b=r;
  } while (fabs(r)>1e-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