3032. 홍준이의 숫자 놀이

3032. 홍준이의 숫자 놀이

문제 요약

두 자연수 A와 B를 정한 후, Ax + By = 1이 되는 x와 y를 계산하는 프로그램을 작성하시오

유클리드 호제법

12345와 123의 최대공약수를 구해보자

즉 a를 b로 나눈 나머지가 r이라했을 때 GCD(a,b) = GCD(b,r)을 이용하여 구현한 것이다.

확장된 유클리드 호제법

일단 초기값으로 x1 = 1, y1 = 0, x2= 0, y2 = 1로 초기화 한다.
그리고 유클리드 호제법으로 구한 나머지들을 세팅한다.
12345 - 123x100 = 45이다. 따라서 1 + (0x-100), 0 + (1x-100)을 세팅한다.
123 - 45x2 = 33이다. 따라서 0 + (1x-2), 1 + (-100x-2)를 세팅한다. 이렇게 가다가 gcd = 3일 때 해당 x,y값을 리턴해주면 된다.

코드

1. 인풋받은 a,b를 세팅한다.
   
   유클리드 호제법 전제조건은 a>b보다 클 때이다. 따라서 인풋받은 b가 a보다 더 클 때 바꿔주고 flg값으로 reverse를 사용한다.

유클리드 호제법 함수 정의

재귀구조를 사용한 유클리드 호제법이다. GCD(a,b) = GCD(b, R(a mod b))값을 이용한 것이다. 그리고 mod값을 stack에 넣어준다.

함수 정의

문제에서 정의한 일차 함수를 정의한다.

확장된 유클리드 호제법

위에서 초기값으로 x1, y1 = 1, 0을 x2,y2 = 0, 1값으로 세팅한 것을 볼 수 있다. 그리고 해당 알고리즘을 코드로 나타내었다.

결과

reverse여부에 따라 출력을 한다.

전체코드

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    a, b = map(int, input().split(" "))
    stack = []
    reverse = False
    if a < b:
        tmp = a
        a = b
        b= tmp
        reverse= True
        
        
    def gcd(a, b):
        if a % b == 0:
            return b
        
        stack.append(a % b)
        return gcd(b, a%b)
    
    
    def graph(x, y):
        return a*x + b*y
    x1,y1 = 1, 0
    x2, y2 = 0, 1
    gcd = gcd(a,b)
    
    while True:
            target = stack.pop(0)
            num1 = graph(x1, y1)
            num2 = graph(x2, y2)
            plus = (target - num1) // num2
            tmp1, tmp2 = x1 + (x2 * plus), y1 + (y2 * plus)
            x1, y1 = x2, y2
            x2, y2 = tmp1, tmp2
            if target == gcd:
                break
    if not reverse:   
        print("#" + str(test_case) + " " + str(x2) + " " + str(y2))
    else:
        print("#" + str(test_case) + " " + str(y2) + " " + str(x2))