Algorithm 공부 #28 - 확장 유클리드 호제법(Extended Euclidean Algorithm)

Algorithm 공부 #27 - 확장 유클리드 호제법

 

 

✏️ 유클리드 호제법

최대공약수 관련 문제들을 풀어봤다면 한번쯤은 접해 봤을 법한 알고리즘

자연수 a와 b가 주어졌을 때 gcd(a,b) 즉 a와 b의 최대공약수를 구할 수 있음

 

a를 b로 나눈 몫을 q라고 하고, 나머지를 r이라 하면 a= bq + r로 나타냄

이때 gcd(a,b) = gcd(b,r)을 만족 

$gcd(a,b)=g$라고 하면, $g|a$, $g|b$ 를 만족하게 되고, $r=a-bq$이므로 $g|(a-bq)=r$ 을 만족

$gcd(b,r)=g$라고 해도, $g|b$, $g|r$ 를 만족하게 되고, $a=bq+r$이므로 $g|(bq+r)=a$ 를 만족

위 식을 이용해서 기존의 $(a,b)$를 $(b,r)$로 축소 해나가게 되면 결국 최종적으로 $(g,0)$의 형태가 나오게 됨 

 

gcd(a,b)를 걸리는 시간은 O(max(log a, log b), 즉 log 자연수 시간내에 최대공약수를 구할 수 있는 효율적인 방법

ex) 120과 76, gcd(120,76)

120 = 76 x 1 + 44이므로 gcd(120,76) = 44

76 = 44 x 1 + 32이므로 gcd(76,44) = 32

44 = 32 x 1 + 12이므로 gcd(44,32) = 12

32 = 12 x 2 + 8이므로 gcd(32,12) = 8

12 = 8 x 1 + 4이므로 gcd(12,8) = 4

8 = 4 x 2 + 0이므로 gcd(8,4) = 0 = gcd(4,0)

즉 gcd(120,76) = gcd(4,0)과 같으므로 120과 76의 최대공약수는 4이다

여기서 알 수 있는 점은 gcd(a,b)=0이 되는 순간 그때의 b값이 두 자연수의 최대공약수가 된다는 점이다

이를 코드로 적용시켜보면 다음과 같다

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

 

 

 

✏️ 확장 유클리드 호제법

이름에서 보면 알 수 있듯이 유클리드 호제법의 확장형이라고 생각하면 된다.

유클리드 호제법은 gcd(a,b)만 구했다면 확장 유클리드 호제법은 gcd(a,b)와 부정 방정식 ax+by=c가 주어질 때

이 방정식을 만족하는 x와 y값을 구할 수 있다

이때, c가 gcd(a,b)의 배수가 아니라면 해가 존재하지 않는다. 그 이유는 쉽게 생각해볼 수 있는데

좌변의 ax+by가 결론적으로 gcd(a,b)의 배수이기 때문이다.

 

c=gcd(a,b)라고 가정하고 a,b,c의 부호에는 제한이 없다고 하자

(x,y)값을 찾기 위해서는 유클리드 호제법의 과정을 역으로 따라가면 된다

 

$a=b{q}_0+r_1$

$b=r_1{q}_1+r_2$

$r_1=r_2{q}_2+r_3$

...

$r_{i-1}=r_i{q}_i+r_{i+1}$

 

유클리드 호제법은 나머지가 0일때 종료되므로 ri-1이 0일때 종료된다

그리고 위의 식을 통해 ri+1 = ri-1 - riqi임을 알 수 있고 c는 ri가 된다

ax + by 꼴로 나타내기 위해서 r0=a, r1=b라고 하면 r0 = a x 1 + b x 0이 되고,

r1 = a x 0 + b x 1이 됨, 계산을 하다 보면 이후의 ri값들도 같은 형태로 나타나게 되고

일반화를 시키면 ri = sia + tib, 이를 ri+1 = ri-1-riqi에 대입시키면

s와 t에 대한 점화식이 다음과 같이 나온다

 

si+1 = si-1 - siqi  /  ti+1 = ti-1 - tiqi

여기서 s는 x로 t는 y로 생각하면 된다

코드로 구현하면 아래와 같다

 

ll exEuclid(int a, int b, int& x, int& y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}

	ll gcd = exEuclid(b, a % b, x, y);
	ll temp = x;

	x = y - (a / b) * x;
	y = temp;

	if (x <= 0) {
		x += b;
		y -= a;
	}
	return gcd;
}

 

이 코드 또한 유클리드 호제법과 마찬가지로 로그 시간내에 계산이 가능

 

 

✏️ 모듈러 연산에서의 곱셉의 역원

백준 문제에서 역원 구하기 문제등을 접할 수 있는데 이런 문제들도 확장 유클리드 호제법을 통해 풀 수 있다

모듈러 연산에서의 곱셉의 역원을 구하는 경우는 ax ≡ 1(mod n)인 x를 찾는 경우라고 할 수 있음

즉 ax+ny=1을 만족하는 정수 순서쌍 (x,y)를 구하는 것과 동일

 

gcd(a,n)이 1이라면 확장 유클리드 호제법을 적용할 수 있고

나머지가 1이 아닌 일반적인 경우 ax ≡b(mod n)인 경우도 해결할 수 있음

 

 

✏️ 백준 문제로 접근