[Python, 파이썬] SWEA 3032. 홍준이의 숫자 놀이

Ax + By = 1이 되는 x와 y를 계산하는 문제

 

 

def extended_euclidean_algorithm(a, b):
    
    # Base case
    if b == 0:
        return a, 1, 0

    # Recursive step
    gcd, x1, y1 = extended_euclidean_algorithm(b, a % b)
    x = y1
    y = x1 - (a // b) * y1

    return gcd, x, y

T = int(input()) # 테스트 케이스의 수 T

for test_case in range(1, T+1):

    a, b = map(int, input().split()) # 서로수 a, b

    answer, x, y = extended_euclidean_algorithm(a, b) # 확장된 유클리드 호제법으로 답을 구함
    print("#%d %d %d" %(test_case, x, y))

 

 

 

[문제풀이]

---

 

솔직히 이 문제, 딱 보자마자 어떻게 하는지 모르겠어서 댓글을 봤다...

그랬더니 확장된 유클리드 호제법으로 풀라 해서 찾아봤더니 이론 이해에 실패함.

그래서 그냥 코드를 외웠다 암기가 짱이야!

Ax + By = K

 

 

확장된 유클리드 호제법은 이 방정식의 해를 구하는 알고리즘이다.

extended_euclidean_algorithm(A, B)를 굴리면 최대공약수, 그리고 방정식 해인 x, y가 반환된다.

이때 반환되는 값은 Ax + By = 1일 때의 해이기 때문에 나온 x, y값에 K를 곱해주면 방정식의 해를 구할 수 있다.