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

/* ３整数 l,m,n に対してその最大公約数 d と
   d=lu+mv+nw をみたす u,v,w を求めるプログラム */

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

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

void gcd(int a, int b, int *d, int *x, int *y)
/* 引数 a,b に対して、最大公約数 d と 
   d=ax+by を満たす 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 l,m,n,d,u,v,w,d1,x1,y1,x2,y2;
  char c[16];

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

  printf("\n実行 :\n");
  gcd(l,m,&d1,&x1,&y1);
  gcd(d1,n,&d,&x2,&y2);
  u=x1*x2;
  v=y1*x2;
  w=y2;
  printf("l = %d\n",l);
  printf("m = %d\n",m);
  printf("n = %d\n",n);
  printf("gcd(l,m,n) = %d",d);
  printf(" = %d * ( %d ) + %d * ( %d ) + %d * ( %d )\n",l,u,m,v,n,w);
}