/* 専門コア情報処理演習教材 test3.c, 2001.12.18 */
/* 2001.12.21 改訂 */
/* コンパイル命令は
gcc -o t3 test3.c
実行コマンドは
t3
です。
*/

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

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

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

main()
{
  int a,b,d,x,y;
  char s[16];

  printf("最大公約数のサンプルプログラムです。\n");
  do{
    printf("ふたつの自然数を入力してください。\n");
    printf("a = ");
    gets(s);
    a=atoi(s);
    printf("b = ");
    gets(s);
    b=atoi(s);
  } while((a<=0)||(b<=0));

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