/* 専門コア情報処理演習教材 test3.c, 2001.1.16 */
/* コンパイル命令は
gcc -o t3 test3.c
*/

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

void gcd(a,b,d,x,y)
int a,b,*d,*x,*y;
{
  int d0,x0,y0,q,r;

  if(b==0){
    *d=a;
    *x=1;
    *y=0;
  }
  else{
    q=a / b;
    r=a-q*b;
    gcd(b,r,&d0,&x0,&y0);
    *d=d0;
    *x=y0;
    *y=x0-q*y0;
  }
}

main()
{
  int tama,mimi,neko,mike,buchi;
  char c[16];

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

  printf("\n実行 :\n");
  gcd(tama,mimi,&neko,&mike,&buchi);
  printf("m = %d\n",tama);
  printf("n = %d\n",mimi);
  printf("gcd(m,n) = %d",neko);
  printf(" = %d * ( %d ) + %d * ( %d )\n",tama,mike,mimi,buchi);
}