확장 유클리드 호제법 (EEA)

유클리드 호제법에서는 최대공약수를 빠르게 찾을 수 있었다.

int gcd(int a, int b){
	if(b==0) return a;
	return gcd(b,a%b);
}

이 때 나오는 최대공약수를 d라고 하자. gcd(a,b) 의 값이 d이다.

우리는 ax + by = d 가 되는 x와 y를 찾고 싶다.

"베주 항등식"에 의하여 ax + by = d를 만족하는 x와 y가 무조건 있다.

 

유클리드 호제법의 과정을 나열해보자.
gcd(a,b) => gcd(b,r2) => gcd(r2,r3) => gcd(r3,r4) ... 이런 과정으로 나아갈 것이다. 
이 과정을 수식으로 나열 해보면,
a = b * q0 + r2       <-------- q0는 a를 b로 나눈 몫이고, r2는 a를 b로 나눈 나머지이다. (q0=a/b , r2=a%b)
b = r2 * q1 + r3
r2 = r3 * q2 + r4
이렇게 나열해 볼 수 있다. a를 r0이라고 하고, b를 r1이라고 하면, 다음과 같이 일반화 할 수 있다.

r[i+1] = r[i-1] - r[i] * q[i]

이 식을 잘 기억 해두자.

아까 a를 r0이라고 하고, b를 r1이라 한다고 했는데, 그렇다면 r0과 r1을 다음과 같이 나타낼 수 있다.
r0 = a * 1 + b * 0
r1 = a * 0 + b * 1
이 식을 또 일반화 시켜서 a의 계수는 s, b의 계수는 t로 나타내 보겠다.

r[i] = a * s[i] + b * t[i]

이 식을 아까 나온 r[i+1] = r[i-1] - r[i] * q[i]에 대입해보면 다음과 같은 식을 얻을 수 있다.

s[i+1] * a + t[i+1] * b = s[i-1] * a + t[i-1] * b - (s[i] * a + t[i] * b) * q[i]
정리하면,
s[i+1] * a + t[i+1] * b = (s[i-1]-s[i]*q[i]) * a + (t[i-1]-t[i]*q[i]) * b

즉, s와 t에 대해 식을 얻을 수 있다.

s[i+1] = s[i-1] - s[i] * q[i]
t[i+1] = t[i-1] - t[i] * q[i]

s와 t는 각각 a와 b의 계수이므로, r[i+1]이 0이 나올 때 까지 반복하면, s[i+1]이 아까 구하고 싶던 x고, t[i+1]이 아까 구하고 싶던 y이다.

이걸 c++로 구현해보았다.

나오는 변수는 
r0, r1, r2
s0, s1, s2
t0, t1, t2
q이다.
r2는 r[i+1]을, r1은 r[i]를, r0은 r[i-1]을 의미하고,
s2는 s[i+1]을, s1는 s[i]를, s0은 s[i-1]을 의미하고,
t2는 t[i+1]을, t1은 t[i]를, t0은 t[i-1]을 의미한다.
q는 r[i-1]과 r[i]를 나눈 몫을 의미한다.

/*
확장 유클리드 알고리즘
GCD(a,b)=d일 때,
ax+by=d를 만족하는 x,y를 찾아야 한다.
*/
#include <bits/stdc++.h>
using namespace std;
pair<int,int> EEA(int a, int b){
	int r0=a, r1=b;
	int s0=1, s1=0;
	int t0=0, t1=1;
	while(r1){
		int q=r0/r1;
		int r2=r0-r1*q;
		r0=r1;
		r1=r2;
		int s2=s0-s1*q;
		s0=s1;
		s1=s2;
		int t2=t0-t1*q;
		t0=t1;
		t1=t2;
	}
	cout << "r0 : " << r0 <<", r1 : "<<r1<<'\n';
	cout << "s0 : " << s0 <<", s1 : "<<s1<<'\n';
	cout << "t0 : " << t0 <<", t1 : "<<t1<<'\n';
	cout << "ax+by=d => "<<a<<"*"<<s0<<"+"<<b<<"*"<<t0<<"="<<r0<<'\n';
	return {s0,t0};
}
int main(){
	int a,b; cin>>a>>b;
	pair<int,int> ans=EEA(a,b);
}