拡張ユークリッドアルゴリズムのCプログラム？

ここでは、Cを使用して実装された拡張ユークリッドアルゴリズムを確認します。拡張ユークリッドアルゴリズムは、GCDを取得するためにも使用されます。これにより、以下のようなxとyの整数係数が見つかります-

𝑎𝑥+𝑏𝑦 = gcd(𝑎,𝑏)

このアルゴリズムでは、次のような再帰呼び出しを使用してgcd（a、b）の値を更新します-gcd（b mod a、a）。アイデアを得るためのアルゴリズムを見てみましょう

アルゴリズム

EuclideanExtended（a、b、x、y）

begin
   if a is 0, then
      x := 0
      y := 1
      return b
   end if
   gcd := EuclideanExtended(b mod a, a, x1, y1)
   x := y1 – (b/a)*x1
   y := x1
   return gcd
end

例

#include <stdio.h>
int EuclideanExtended(int a, int b, int* x, int* y) {
   if (a == 0) {
      *x = 0;
      *y = 1;
      return b;
   }
   int xtemp, ytemp; // To store results of recursive call
   int res = EuclideanExtended(b % a, a, &xtemp, &ytemp);
   *x = ytemp - (b / a) * xtemp;
   *y = xtemp;
   return res;
}
int main() {
   int x, y;
   int a = 60, b = 25;
   int res = EuclideanExtended(a, b, &x, &y);
   printf("gcd(%d, %d) = %d", a, b, res);
}

出力

gcd(60, 25) = 5