#include<stdio.h>
#include<alloc.h>
#include<conio.h>

#define nuovo(a) a=(lista *)malloc(sizeof(lista *));\
					  a->c=NULL;a->p=NULL
#define iunta(a) a->c=(lista *)malloc(sizeof(lista *));\
					  a->c->p=a;\
					  a=a->c;\
					  a->c=NULL;
#define ini(a,n,in) a->v=n;a->i=in
#define pr(a) a=a->c
#define pausa while(!kbhit){}getch()

typedef struct lista{int v,i;struct lista *c,*p;};

int main(void);
int giu(lista *,lista *,lista *,lista *);
void su(lista *,lista *,lista *,lista *);
void stampa(lista *);
void libera(lista *);

int main (void){
lista *r,*q,*n,*d;
int n1,n2,app;
char com='s';
clrscr;
while(com=='s'){
 printf("primo numero   : ");scanf("%d",&n1);
 printf("secondo numero : ");scanf("%d",&n2);
 if (n2>n1){
	app=n1;
	n1=n2;
	n2=app;
 }
 nuovo(n);
 ini(n,n1,1);
 nuovo(d);
 ini(d,n2,1);
 nuovo(q);
 ini(q,0,1);
 nuovo(r);
 ini(r,0,1);
 printf("\nIl Massimo Comun Divisore %c %d\n",138,giu(n,q,d,r));
 su(n,q,d,r);
 pausa;
 libera(n);
 libera(q);
 libera(d);
 libera(r);
 fflush(stdin);
 printf("\nancora?");scanf("%c",&com);
}
return(0);
}

void libera(lista *a){
while(a->c!=NULL){
  a=a->c;
  a->p->c=NULL;
  free(a->p);
  a->p=NULL;
}
free(a);
}

int giu(lista *n,lista *q,lista *d,lista *r){
int ind=1,mcd;
void *in,*iq,*id,*ir;
in=n;iq=q;id=d;ir=r;
q->v=n->v/d->v;
r->v=n->v%d->v;
printf("%5d=%5d X %5d + %5d\n",n->v,d->v,q->v,r->v);pausa;
while(r->v!=0){
  ind++;
  iunta(n);ini(n,d->v,ind);
  iunta(d);ini(d,r->v,ind);
  iunta(r);
  iunta(q);
  q->v=n->v/d->v;q->i=ind;
  r->v=n->v%d->v;r->i=ind;
  printf("%5d=%5d X %5d + %5d\n",n->v,d->v,q->v,r->v);
  pausa;
}
mcd=d->v;
n=(lista *)in;q=(lista *)iq;d=(lista *)id;r=(lista *)ir;
return(mcd);
}

void su(lista *n,lista *q,lista *d,lista *r){
int ind,mcd,a,b,j,k,app;
if (r->v==0){
  printf("I due numeri sono divisibili quindi la soluzione ovvia %c:%d=%dX1\n",138,d->v,d->v);
}
else{
while (r->v!=0){r=r->c;}
ind=r->i-1;
r=r->p;
for (int cont=1;cont<ind;cont++){
  pr(n); pr(q); pr(d);
}
mcd=r->v;
a=n->v;
b=d->v;
if (a<b){
  app=a;a=b;b=a;
}
j=-(q->v);
k=1;
printf("\n    %4d=%4d X %4d + %4d X %4d",mcd,a,k,b,j);
while(r->p!=NULL){
n=n->p;d=d->p;q=q->p;r=r->p;
pausa;
printf("  &  %5d=%5d + %5d X %5d",b,n->v,d->v,-q->v);
b=a;a=n->v;
app=k;
k=j;
j=app+(j*(-q->v));
pausa;
printf("\n==> %4d=%4d X %4d + %4d X %4d",mcd,b,j,a,k);
}
}
}

void stampa(lista *a){
while (a!=NULL){
printf("%4d",a->v);
a=a->c;
}
}
