#include<stdio.h>
#include<stdlib.h>

void  err(char s[]) {
  printf("\n !!! %s !!!\n\n", s);
  exit(1);
}

void  dzielnat(int n, int k, int* q, int* r) {
  int a=k;
  while (a <= n)
    a = a<<1;
  *r=n; *q=0;
  while (a > k) {
    a = a>>1; *q = (*q)<<1;
    if (*r >= a) {
      *r = *r-a; *q = *q+1;
    }
  }
}

void  dziel(int n, int k, int* q, int* r) {
  if (k == 0)  err("dzielenie przez 0");
  else {
    dzielnat( (n<0 ? -n : n), (k<0 ? -k : k), q, r);
    if (n < 0)  {*q = -*q; *r = -*r;}
    if (k < 0)  *q = -*q;
    if (*r < 0) {
      if (k > 0)  {*q = *q-1; *r = *r+k;}
      else  {*q = *q+1; *r = *r-k;}
    }
  }
}

void euk(int n, int k, int* x, int* y, int* z) {
  int  a, b, c, d, e, f, zamienic=0;
  if (n < k) {int p; p=n; n=k; k=p; zamienic=1;}
  /* teraz  n >= k */
  printf("\n %5i ==  %5i * (    1) + %5i * (    0)", n, n, k);
  printf("\n %5i ==  %5i * (    0) + %5i * (    1)", k, n, k);
  a=n; b=1; c=0;  /* a == n*b + k*c */
  d=k; e=0; f=1;  /* d == n*e + k*f */
  while (d != 0) {
    int  q, r, e1, f1;
    dziel(a, d, &q, &r);
    a = d;  d = r;
    e1 = e;  e = b-e*q;  b = e1;
    f1 = f;  f = c-f*q;  c = f1;
    printf("   |  * (%5i)\n %5i ==  %5i * (%5i) + %5i * (%5i)",
           -q, r, n, e, k, f);
  }
  if (zamienic) {
    int p;
    p=n; n=k; k=p;
    p=b; b=c; c=p;
  }
  *x = a; *y = b; *z = c;
}

int main () {
  int  n, k, x, y, z;
  printf("\n ALGORYTM EUKLIDESA");
  printf("\n (tylko dla tych, ktorzy wiedza, jak to dziala,");
  printf("\n  dla przyspieszenia rachunkow)\n\n");
  printf(" n == "); scanf("%i", &n);
  printf(" k == "); scanf("%i", &k);
  euk(n,k,&x,&y,&z);
  printf(
    "\n\n nwd(%5i,%5i) == %5i == %5i * (%5i) + %5i * (%5i)\n\n",
    n,k, x, n, y, k, z);
  return 0;
}