/* euclid.c 
ユークリッドのアルゴリズム拡張版
*/

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

/* ユークリッドのアルゴリズム拡張版、数列を作る version */
int euclid1(int a, int b, int *x, int *y)
{
	int r[64],xx[64],yy[64],q,n=1;
	r[0] =a;
	r[1] =b;
	xx[0]=1;
	xx[1]=0;
	yy[0]=0;
	yy[1]=1;
	while(r[n]!=0){
		n++;
		q=r[n-2]/r[n-1];
		r[n] =r[n-2] -q*r[n-1];
		xx[n]=xx[n-2]-q*xx[n-1];
		yy[n]=yy[n-2]-q*yy[n-1];
	}
	if(r[n-1]>=0){
		*x=xx[n-1];
		*y=yy[n-1];
		return(r[n-1]);	
	}
	else{
		*x=-xx[n-1];
		*y=-yy[n-1];
		return(-r[n-1]);
	}
}

/* ユークリッドのアルゴリズム拡張版、メモりを節約する version */
int euclid2(int a, int b, int *x, int *y)
{
	int r0=a,r1=b,r2,x0=1,x1=0,x2,y0=0,y1=1,y2,q;
	while(r1!=0){
		q=r0/r1;
		r2=r0-q*r1;
		x2=x0-q*x1;
		y2=y0-q*y1;
		// 番号を振り替える
		r0=r1;
		r1=r2;
		x0=x1;
		x1=x2;
		y0=y1;
		y1=y2;
	}
	if(r0<0){
		r0=-r0;
		x0=-x0;
		y0=-y0;
	}
	*x=x0;
	*y=y0;
	return(r0);
}

/* ユークリッドのアルゴリズム拡張版、再帰呼出しを用いる version */
int euclid3(int a, int b, int *x, int *y)
{
	int q,r,d0,x0,y0;
	if(b==0){
		if(a>=0){
			*x=1;
			*y=0;
			return(a);
		}
		else{
			*x=-1;
			*y=0;
			return(-a);
		}
	}
	else{
		q=a/b;
		r=a-q*b;
		d0=euclid3(b,r,&x0,&y0);
		*x=y0;
		*y=x0-q*y0;
		return(d0);
	}
}

main()
{
	int a,b,d,x,y;
	printf("input  a  and  b:\n");
	printf("a = ");
	scanf("%d",&a);
	printf("b = ");
	scanf("%d",&b); 
  
	printf("\n");
	printf("euclid1 :\n");
	d=euclid1(a,b,&x,&y);
	printf("gcd(%d,%d) = %d = (%d)*(%d)+(%d)*(%d)\n",a,b,d,a,x,b,y);
	printf("check : ");
	printf("(%d)*(%d)+(%d)*(%d) = %d\n",a,x,b,y,a*x+b*y);
  
	printf("\n");
	printf("euclid2 :\n");
	d=euclid2(a,b,&x,&y);
	printf("gcd(%d,%d) = %d = (%d)*(%d)+(%d)*(%d)\n",a,b,d,a,x,b,y);
	printf("check : ");
	printf("(%d)*(%d)+(%d)*(%d) = %d\n",a,x,b,y,a*x+b*y);    
  
	printf("\n");
	printf("euclid3 :\n");
	d=euclid3(a,b,&x,&y);
	printf("gcd(%d,%d) = %d = (%d)*(%d)+(%d)*(%d)\n",a,b,d,a,x,b,y);
	printf("check : ");
	printf("(%d)*(%d)+(%d)*(%d) = %d\n",a,x,b,y,a*x+b*y);
}

/* 実行例

input  a  and  b:
a = 12345
b = 6789

euclid1 :
gcd(12345,6789) = 3 = (12345)*(-903)+(6789)*(1642)
check : (12345)*(-903)+(6789)*(1642) = 3

euclid2 :
gcd(12345,6789) = 3 = (12345)*(-903)+(6789)*(1642)
check : (12345)*(-903)+(6789)*(1642) = 3

euclid3 :
gcd(12345,6789) = 3 = (12345)*(-903)+(6789)*(1642)
check : (12345)*(-903)+(6789)*(1642) = 3

*/