확장 유클리드 호제법

유클리드 호제법을 활용하여 최대공약수를 구할 수 있다.

그리고 유클리드 호제법을 응용하여 일차방정식의 해를 쉽게 구할 수 있는 방법이 확장 유클리드 호제법 방법이다.

 

ax + by = c 라는 방정식이 있다고 하자.

1. 좌변과 우변의 공약수가 있는 경우 약분을 하고, 우변의 값이 gcd(a,b)의 배수인 경우 gcd(a,b)로 변경한 후 해를 구한다. 그래서 gcd(a,b)가 서로소인 경우 우변을 1로 놓을 수 있다.

반대로 예를들어 162x+42y=19의 경우 19가 gcd(162,42)=6의 배수가 아니므로 해가 존재하지 않는다.

 

a,b,c가 입력값으로 주어져 있다고 하자 먼저 확장 유클리드 호제법을 적용하기 전에 gcd(a,b)의 값이 1이라면 

그렇다면 먼저 방정식을

ax + by =1 로 변환 후에

 

다음의 방정식을 이용하여 s(x의 해 ), t(y의 해), r(나머지), q(몫) 과 관련된 표를 만들 수 있다.

r(현재)=r(전전)%r(전)

q(현재)=r(전전)/r(전)

s(현재)= s(전전)-s(전)*q

t(현재)= t(전전)-t(전)*q

	s	t	r	q
전전	1	0	..
전	0	1	..
현재	2	1	r2%r1	r2/r1
그다음			0

그리고 이 표가 채워지면서 r=0으로 바뀌는데 그때! 전의 s와 t의 값, 표에서는 2와 1이 각각 방정식의 x,y의 해가 된다.

이 해를 이용하면 a(x+(b/gcd(a,b))*t) + b(y-(a/gcd(a,b))*t) = c 라는 식을 유도할 수 있고

이때 x+(b/gcd(a,b))*t, y-(a/gcd(a,b))*t 가 x와 y의 확장된 해라고 할 수 있다. 그래서 이 조건을 만족시키는 일차방정식의 해인 x와y의 순서쌍을 여러가지 구할 수 있게된다.

 

관련문제

백준3955 캔디분배:https://www.acmicpc.net/problem/3955

이 문제에서 방정식 -ax + by =1 이라는 방정식이 세워지는데

b=1인 경우 x의 최솟값이 1이라고 했을 때 y의 값은 10^9을 넘으면 안되기 때문에 y=1+a 의 값또한 10^9을 넘으면 안된다. 

 

그리고 a=1인 경우 x의 최솟값이 0부터 시작이므로 y는 1부터 해가 될 수 있다. 그래서 이떄는 y의 값을 1로 출력하면 된다.

 

마지막으로 gcd(a,b)의 값이 1이 아니면 gcd의 배수가 1이 될 수 없으므로 해가 존재하지 않게 된다.

따라서 반드시 gcd(a,b) = 1 이여야 한다!

 

소스코드