확장 유클리드 알고리즘

아래 영상을 참고해 작성했습니다.

https://www.youtube.com/watch?v=PmwLXveLtqc 

---

정의

유클리드 호제법을 확장한 알고리즘 입니다.

https://kdr06006.tistory.com/21

유클리드 호제법

 

ax + by = c

c의 값이 gcd(a, b)의 배수일 때만 (x, y)가 정수해를 갖습니다.

 

즉, 확장 유클리드 알고리즘은 위의 식을 만족하는 정수해 (x, y)를 찾는 문제입니다.

---

증명

아래 블로그로 대체하겠습니다.

https://baeharam.github.io/posts/algorithm/extended-euclidean/

[알고리즘] 확장 유클리드 알고리즘

---

과정

유클리드 호제법 과정을 따라가면서 (x, y) 값을 구할 수 있습니다.

12345x + 123y = 3의 (x, y) 정수해를 구해보겠습니다.

---

초기 세팅

(x, y)가 (1,0), (0,1)인 경우 값이 아래와 같습니다.

이제 이 표를 하나씩 채워보겠습니다.

---

다음 빈칸에 앞의 수 12345, 123의 나머지를 위치시키고 싶습니다.

왼쪽 그림은 유클리드 호제법 과정입니다.

 

12345 - 100 * 123 = 45 가 나옵니다.

=> 첫번째 식 - 100 * 두번째 식 = 45

=> 첫번째 식 - 몫 * 두번째 식 = 45

---

그 다음 칸 역시 앞의 두 수(123, 45)의 나머지가 오도록 하고 싶습니다.

123 - 2 * 45 = 33

=> 두번째 식 - 2 * 세번째 식 = 33

=> 두번째 식 - 몫 * 세번째 식 = 33

---

그 다음칸 역시 나머지가 오도록 하고 싶습니다.

45 - 1 * 33 = 12

=> 세번째 식 - 1 * 네번째 식 = 12

=> 세번째 식 - 몫 * 네번째 식 = 12

---

그 다음칸 역시 나머지가 오도록 하고싶습니다.

33 - 2 * 12 = 9

=> 네번째 식 - 2 * 다섯번째 식

=> 네번째 식 - 몫 * 다섯번째 식

---

다음 칸 역시 나머지가 오도록 하고 싶습니다.

12 - 1 * 9 = 3

=> 다섯번째 식 - 1 * 여섯번째 식

=> 다섯번째 식 - 몫 * 여섯번째 식

---

(x, y)의 정수해는 (11, -1104)가 나왔습니다.

12345 * (11) + 123 * (-1104) = 3

---

코드

#include <cstdio>
#include <algorithm>
using namespace std;

struct Pii {
	int first, second;

	Pii operator*(int m) {
		return { first * m, second * m };
	}

	Pii operator-(Pii O) {
		return { first - O.first, second - O.second };
	}
};

void extended_gcd(Pii number, Pii p1, Pii p2) {
	printf("x = %d, y = %d, ans = %d\n", p1.first, p1.second, number.first);
	if (number.second == 0) return;

	int q = number.first / number.second;
	int r = number.first % number.second;
	Pii pNew = p1 - p2 * q;
	extended_gcd({ number.second, r }, p2, pNew);
}

int main()
{
	freopen("input.txt", "r", stdin);

	int A, B;
	scanf("%d %d", &A, &B);
	if (A < B) swap(A, B);

	extended_gcd({ A, B }, { 1, 0 }, { 0, 1 });
}