확장된 유클리드 호제법 구현 in python

이렇다고 한다..

 

최대한 직관적으로 구현하고자 했다 (물론 더 간단한 방법도 있겠지만)

계수 (a,b,c,d) 간 관계식을 이용해서 코드를 짜면 될 것 같다

def extended_euclidean(X,Y):
    if X<Y:
        b, a, GCD = extended_euclidean(Y,X)
    
    x = X
    y = Y
    a = d = 1
    b = c = 0

    while y>0:
        q = x//y
        r = x%y
        if r==0: break # GCD 구해짐
        x,y,a,b,c,d = y,r,c,d,a-q*c,b-q*d

    return c,d,y


x,y = map(int, input().split())
a,b,GCD = extended_euclidean(x, y)

print(f'{a} * {x} + {b} * {y} = {GCD}')

 

물론 파이썬 라이브러리를 사용해서 개 ez하게 구할 수도 있다

from gmpy2 import gcdext

gcd, s, t = gcdext(79, 61)

gmpy2 라이브러리의 gcdext() 함수