/* t3_4.c ( PASCAL講座 sample program )
ユークリッドのアルゴリズム

２整数 a, b の最大公約数 d = gcd(a,b) と、
　　d = a x + b y
を満たす整数 x, y を高速に求める。

コンパイル命令は
gcc t3_4.c -o t3_4

実行命令は
t3_4
*/

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

int euclid(int m, int n, int *u, int *v)
{
  int g,u0,v0,q,r;

  if(n==0){
    if(m>=0){ *u=1; *v=0; return m; }
    else{ *u=-1; *v=0; return -m; }
  }
  else{
    q=m/n;
    r=m-q*n;
    g=euclid(n,r,&u0,&v0);
    *u=v0;
    *v=u0-q*v0;
    return g;
  }
}

main()
{
  int a,b,d,x,y;

  printf("最大公約数のサンプルプログラムです。\n");
  printf("ふたつの自然数を入力してください。\n");
  printf("a = ");
  scanf("%d",&a);
  printf("b = ");
  scanf("%d",&b);

  d=euclid(a,b,&x,&y);
  printf("gcd(a,b) = %d",d);
  printf(" = ( %d ) * ( %d ) + ( %d ) * ( %d )\n",a,x,b,y);
}