/* 専門コア情報処理演習教材 test3.c */

/* 自然数の最大公約数を求めるユークリッドのアルゴリズム
（関数・再帰呼び出し・ポインタ等を用いています。） */

/*
コンパイル命令は
gcc -o t3 test3.c
実行コマンドは
./t3
*/

#include<stdio.h>	// ヘッダ・ファイルを読み込みます。
#include<stdlib.h>

int gcd(int m, int n,int *u, int *v)
/* 引数 a,b に対して、最大公約数 d と 
   d=ax+by を満たす x,y を計算する関数の定義 */
{
  int g0,u0,v0,q,r;

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

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");
  d=gcd(a,b,&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);
}