확장 유클리드 알고리즘을 위한 C 프로그램?

여기에서 우리는 C를 사용하여 구현된 확장된 유클리드 알고리즘을 볼 것입니다. 확장된 유클리드 알고리즘은 또한 GCD를 얻는 데 사용됩니다. 이것은 아래와 같이 x와 y의 정수 계수를 찾습니다 -

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

여기 이 알고리즘에서 gcd(b mod a, a)와 같은 재귀 호출을 사용하여 gcd(a, b)의 값을 업데이트합니다. 아이디어를 얻기 위한 알고리즘을 살펴보겠습니다.

알고리즘

유클리드 확장(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