파이썬 확장 유클리드 알고리즘(Extended Euclidean Algorithm) 구현 - 공부하는 도비

2021.05.21 - [파이썬/프로젝트] - [파이썬] 유클리드 알고리즘(Euclidean Algorithm) - 공부하는 도비

[파이썬] 유클리드 알고리즘(Euclidean Algorithm) - 공부하는 도비

gcd(최대공약수) 를 계산하는 알고리즘을 저번 글에서 소개했었습니다. 

 

이번엔, 확장된 유클리드 알고리즘 코드를 보여드릴까 합니다. 

 

* 확장 유클리드 알고리즘 

: 두 정수 a, b 가 주어질 때, 다음을 만족하는 다른 두 정수 s 와 t 를 계산한다.

 

간단히 말하면, a 와 b 에 어떤 수를 더하고, 빼고 해서 결국 두 a, b 의 최대공약수를 만족하는 s 와 t 를 찾는 것입니다. 

 

저번 글에서 나온 유클리드 알고리즘을 활용합니다.

 

# Euclidean Algorithm

import sys

a, b = map(int, sys.stdin.readline().split())

a_temp = a
b_temp = b
print(" ")
q, r, t, r = 0, 0, 0, 0

s_1, s_2 = 1, 0
t_1, t_2 = 0, 1
if a < b : 
        a, b = b, a         # swap

while(True):
    
    q = a // b
    r = a - (q*b)
    s = s_1 - (q * s_2)
    t = t_1 - (q * t_2)

    print(a ,'=', q, '*', b, '+', r)    
    
    if r == 0:
        print("\ngcd = ", b)
        print("s : ", s_2, ", t : ", t_2)
        if b == 1:
            print("relatively prime")
        break

    a = b
    b = r
    s_1 = s_2
    s_2 = s
    t_1 = t_2
    t_2 = t   

print(s_2 ,"*",  a_temp, "+", t_2, "*", b_temp, "=", b)

일차방정식으로 나타낼 수 있게 됩니다