[알고리즘] 20일차 (Ax+By=C) #백준21568번

07-4 확장 유클리드 호제법

• 유클리드 호제법의 목적이 두 수의 최대 공약수를 구하는 것이라면, 확장 유클리드 호제법의 목적은 방정식의 해를 구하는 것이다.
• ax + by = c (a, b, c, x, y는 정수)
• 위 방정식은 c % gcd(a, b) = 0인 경우에만 정수해를 가진다.
• 다시 말해, c가 a와 b의 최대 공약수의 배수인 경우에만 정수해를 가진다.

[확장 유클리드 호제법의 원리 이해하기]
ex) 5x + 9y = 2

1. 우선 5x + 9y = 2가 정수해를 갖게 하는 c의 최솟값이 gcd(5, 9)라는 것을 적용하여 식을 다시 놓는다. gcd(5, 9) = 1이므로 5x + 9y = 1로 식을 다시 놓고 다음 단계를 진행한다.
2. a, b로 유클리드 호제법을 반복 실행하며 몫, 나머지를 저장한다. 반복은 나머지가 0이 되면 중단한다.
3. 반복으로 구한 나머지와 몫을 이용하여 거꾸로 올라가며,
   x = y', y = x' - y' * q를 계산한다. x'는 이전 x, y'는 이전 y를 의미하고, q는 현재 보고 있는 몫을 의미한다. 이때, 처음 시작하는 x, y는 이전 x와 이전 y가 없으므로 각각 1, 0으로 지정하여 역계산을 진행한다.
4. 이렇게 재귀 방식으로 알아낸 최종 x, y는 ax + by = gcd(a, b)를 만족한다. 그리고 c / gcd(a, b) = K를 가정하면 최초 방정식의 해는 Kx, Ky로 간단히 구할 수 있다. 3번 과정에서 찾은 x는 2, y는 -1이고 K값을 구하면 2(c값) / 1(최대 공약수) = 2가 되므로 2의 값을 기존의 x(2), y(-1) 값에 각각 곱한다. 이에 따라, 최초 방정식의 해는 4, -2가 된다.

📌 문제 045) Ax+By=C

시간 제한 1초, 골드 I, 백준 21568번

A, B, C가 주어졌을 때, Ax+By=C를 만족하는 (x, y)중에서 다음을 만족하는 것을 아무거나 찾아보자.

• x, y는 정수
• -1,000,000,000 ≤ x, y ≤ 1,000,000,000
• 1,000,000 ≤ A, B, C ≤ 1,000,000
• A, B ≠ 0

입력

첫째 줄에 정수 A, B, C가 주어진다.

1 2 3 # A B C

출력

Ax+By=C를 만족하는 x, y를 공백으로 구분해 출력한다. 문제의 조건을 만족하는 (x, y)가 존재하지 않는 경우에는 -1을 출력한다.

3 0

1단계 문제 분석

• 앞에서 배운 '확장 유클리드 호제법'을 그대로 구현하면 된다. 핵심 이론을 다시 한번 정확하게 학습하고 적용해보자.

1. C의 값이 A와 B의 최대 공약수의 배수 형태인지 확인한다. 최대 공약수의 배수 형태라면 C의 값을 최대 공약수로 변경한다. 최대 공약수의 배수 형태가 아니라면 -1을 출력한 후, 프로그램을 종료한다.
2. A와 B에 관해 나머지가 0이 나올 때까지 유클리드 호제법을 수행한다.
3. 나머지가 0이 나오면 x = 1, y = 0으로 설정한 후, 2번 과정에서 구한 몫들을 식(x = y', y = x' - y' * 몫)에 대입하면서 역순으로 계산한다.
4. 최종으로 계산된 x, y 값에 C를 x와 y의 최대 공약수로 나눈 값을 각각 곱해 방정식의 해를 구한다.

2단계 슈도 코드

a(1번째 수) b(2번째 수) c(3번째 수)

# 최대 공약수 gcd() 함수 구현
gcd(a, b):
	if b가 0이면:
    	a가 최대 공약수
    else:
    	gcd(작은 수, 큰 수 % 작은 수) # 재귀 함수 형태로 구현

# 유클리드 호제법 함수 구현
Execute(a, b):
	if b == 0: 재귀 함수를 중단하고, x, y를 각각 1, 0으로 설정하여 return
    q(a를 b로 나눈 몫)
    Execute(b, a % b) # 재귀 함수
    x = y', y = x' - y' * 몫을 계산하는 역산 로직 구현
    # 재귀에서 빠져나오는 영역에서 실행하면 자연스럽게 역순이 됨
    계산된 x y return

최대 공약수 = gcd(a, b)

if c가 최대 공약수의 배수가 아니면:
	-1 출력
else:
	나머지(b)가 0이 될 때까지 재귀 함수를 호출하는 유클리드 호제법 함수 호출
    결괏값에 c/최대 공약수의 값을 곱한 후 해당 값을 출력

3단계 코드 구현

a, b, c = map(int, input().split())
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

def Execute(a, b):
    ret = [0] * 2
    if b == 0:
        ret[0] = 1
        ret[1] = 0
        return ret
    q = a // b
    v = Execute(b, a % b) # 재귀 형태로 유클리드 호제법 수행
    ret[0] = v[1] # 역순으로 올라오면서 x, y를 계산하는 로직
    ret[1] = v[0] - v[1] * q
    return ret

mgcd = gcd(a, b)

if c % mgcd != 0:
    print(-1)
else:
    mok = int(c / mgcd)
    ret = Execute(a, b)
    print(ret[0] * mok, end=' ')
    print(ret[1] * mok)