#include <stdio.h>

/* Swaps two integers */
void swap(int *a, int *b)
{
	int t;

	t = *a;
	*a = *b;
	*b = t;
}

/* Computes the extended gcd of two input numbers
 * n and m. In other words, finds the smallest positive
 * number d, for which there exist numbers e and f
 * such that d = e * n + f * m.
 * Returns the gcd d of the numbers, and the
 * coefficients of the linear combination are stored
 * in *e and *f.
 */
int compute_ext_gcd( int n, int m, int *e, int *f)
{
    int a = n; // initialize a to n
    int b = m; // initialize b to m
    int e_a = 1; // a = e_a * n + f_a * m
    int f_a = 0;
    int e_b = 0; // b = e_b * n + f_b * m
    int f_b = 1;
   
    /* The invariant of the loop is:
     * (1) gcd(a, b) = gcd(n, m)
     * (2) a = e_a * n + f_a * m
     * (3) b = e_b * n + f_b * m
     */

    for (; 1; ) {
       if (a < b) { // ensure that a is bigger by swapping
          swap(&a, &b);
	  swap(&e_a, &e_b);
	  swap(&f_a, &f_b);
       }

       if (a % b == 0) { // b is the gcd
          *e = e_b;
          *f = f_b;
          return b; // b = e_b * n + f_b * m
       }

       /* Replace a by a % b. We need to modify e_a and f_a as follows.
        * Since a = (a / b) * b + (a % b), (a % b) = a - (a/b) * b 
	* 	  = e_a * n + f_a * m - (a/b) (e_b * n + f_b * m)
        *         = (e_a - (a/b) * e_b) * n + (f_a - (a/b) * f_b) * m.
        */
       e_a = e_a - (a/b) * e_b;
       f_a = f_a - (a/b) * f_b;
       a = a % b;
    }
}


int main()
{
	int n;
	int m;
	int e;
	int f;
	int d;

	printf("Enter the two numbers: ");
	scanf("%d %d", &n, &m);

	d = compute_ext_gcd(n, m, &e, &f);

	printf("gcd = %d = %d * %d + %d * %d\n", d, e, n, f, m);
}