확장된 유클리드 알고리즘(extended euclidean algorithm) 구현해보면서 익히기

1. 베주 항등식(Bézout's Identity)

 

적어도 하나가 0이 아닌 두 정수 a,b에 대하여 $$ax+by = gcd(a,b)$$를 만족하는 정수해 x,y가 반드시 존재한다.

 

여기서 정수해 x,y는 유일하지 않다.

 

왜냐하면, 양변에 ab를 더하고 빼보면 $$ax+ab + by-ab = gcd(a,b)$$이므로, $$a(x+b) + b(y-a) = gcd(a,b)$$이므로, (x,y)가 정수해라면, (x+b,y-a)도 정수해가 된다.

 

 

2. 유클리드 알고리즘(Euclidean algorithm)

 

최대공약수를 빠르게 구하는 알고리즘 - 유클리드 호제법 (tistory.com)

최대공약수를 빠르게 구하는 알고리즘 - 유클리드 호제법

 

두 양의 정수 a,b에 대하여, a>b이고 a = bq + r이라고 하자. 그러면 a,b의 최대공약수는 b,r의 최대공약수와 같다.

 

만약 r = 0이면, a,b의 최대공약수는 b이다.

 

 

3. 유클리드 알고리즘으로 최대공약수를 구하기

 

a를 b로 나누면, $a=bq_{0} + r_{0}$

 

그리고, a = b, $b = r_{0}$로 바꾸고, 다시 a를 b로 나누면.. $b = r_{0}q_{1} + r_{1}$

 

그리고 $a=r_{0}$, $b=r_{1}$로 바꾸고 다시 a를 b로 나누면... $r_{0} = r_{1}q_{2} + r_{2}$

 

이를 반복적으로 적용하면...

 

언젠가는 $r_{n+1} = 0 $이 되어 $r_{n-1} = r_{n}q_{n+1}$이 된다.

 

그러면, 최대공약수는 $r_{n}$

 

#유클리드 호제법

def gcd(a,b):
    
    while b != 0:
        
        a,b = b,a%b
    
    return a

 

 

4. 확장된 유클리드 알고리즘(extended euclidean algorithm)

 

베주 항등식의 정수해 x,y를 찾는 알고리즘이다.

 

두 수 a,b의 최대공약수를 구하기 위해 유클리드 알고리즘을 적용하는 과정에서, 

 

$r_{n-1} = r_{n}q_{n+1}$까지 구해서, 최대공약수 $gcd(a,b) = r_{n}$까지 구했다고 하자.

 

베주항등식으로부터, 최대공약수 $r_{n}$은 두 정수 a,b에 대하여 $ax+by$로 나타낼 수 있다.

 

초기값 $r_{0} = a$, $r_{1} = b$라고 하자. 

 

그러면 

 

$$r_{0} = a \times 1 + b \times 0$$

 

$$r_{1} = a \times 0 + b \times 1$$

 

그런데, 유클리드 호제법에서 $r_{n-2} = r_{n-1}q_{n} + r_{n}$ 이므로, $r_{n} = r_{n-2} - r_{n-1}q_{n}$

 

n = 2를 대입해서.. $$r_{2} = r_{0} - r_{1}q_{2} = a - bq_{2}$$

 

n = 3을 대입해서.. $$r_{3} = r_{1} - r_{2}q_{3} = b - (a-bq_{2})q_{3} = -aq_{3} + b(q_{2}q_{3}+1)$$

 

이걸 반복적으로 수행하면..

 

모든 음이 아닌 정수 n에 대하여 $r_{n} = as_{n} + bt_{n}$의 형태로 나타낼 수 있다.

 

그러면 2가지 식을 얻었다.

 

$$r_{n} = as_{n} + bt_{n}$$

 

$$r_{n} = r_{n-2} - r_{n-1}q_{n}$$

 

그러면, $$r_{n-2} - r_{n-1}q_{n} = as_{n} + bt_{n}$$

 

$r_{n} = as_{n} + bt_{n}$으로부터, $$r_{n-2} = as_{n-2} + bt_{n-2}$$와 $$r_{n-1} = as_{n-1} + bt_{n-1}$$을 얻는다.

 

그러므로, $$as_{n-2} + bt_{n-2} - q_{n}(as_{n-1} + bt_{n-1}) = as_{n} + bt_{n}$$

 

양변은 a,b에 대한 항등식이다. 그래서 좌변을 a,b에 대해 정리하면..

 

$$a(s_{n-2} -q_{n}s_{n-1}) + b(t_{n-2} - q_{n}t_{n-1}) = as_{n} + bt_{n}$$

 

그러므로, 두 식을 얻는다.

 

$$s_{n} = s_{n-2} - q_{n}s_{n-1}$$

$$t_{n} - t_{n-2} - q_{n}t_{n-1}$$

 

따라서 다음과 같은 식을 얻었다.

 

$$r_{n} = r_{n-2} - q_{n}r_{n-1}$$

$$s_{n} = s_{n-2} - q_{n}s_{n-1}$$

$$t_{n} = t_{n-2} - q_{n}t_{n-1}$$

 

초기값은 n = 0 , n = 1일때 다음과 같이 설정한다면..

 

$r_{0} = a$, $r_{1} = b$로 설정한다면...

 

$$r_{n} = as_{n} + bt_{n}$$으로부터, $s_{0} = 1$, $t_{0} = 0$이고 $s_{1} = 0$, $t_{1} = 1$

 

 

5. 구현 예시

 

위에서 제시한 점화식을 이용해서 $r_{n}$과 $s_{n}$, $t_{n}$을 구하는 확장된 유클리드 알고리즘을 그대로 구현해보면 다음과 같다

 

def extended_gcd(a,b):
    
    #초기값 설정
    #r0,r1
    r = [a,b]
    
    #s0,s1
    s = [1,0]
    
    #t0,t1
    t = [0,1]
    
    #계속 나누다가, r[-1]이 0이 되면 반복문 종료
    while r[-1] != 0:
        
        q_n = (a_n//b_n) #a를 b로 나눌때 몫
        
        #r(n) = r(n-2) - r(n-1)q(n)
        r_n = r[-2] - r[-1]*q_n
        s_n = s[-2] - s[-1]*q_n
        t_n = t[-2] - t[-1]*q_n
        
        r.append(r_n)
        s.append(s_n)
        t.append(t_n)
    
    #r[-1]은 0이고, r[-2]가 gcd
    return r[-2],s[-2],t[-2]

 

 

혹은 조금 더 깔끔하게? 다음과 같이 구현해볼 수 있다

 

위에서 보인 바와 같이 (s -> x, t -> y로 나타냄)

 

모든 음이 아닌 정수 n에 대하여 $r_{n} = ax_{n} + by_{n}$의 형태로 나타나고,

 

$$x_{n} = x_{n-2} - q_{n}x_{n-1}$$

$$y_{n} = y_{n-2} - q_{n}y_{n-1}$$

 

이다.

 

 $x_{0} = 1$, $y_{0} = 0$이고 $x_{1} = 0$, $y_{1} = 1$으로 설정하면,

 

#반복문

def iterative_extended_gcd(a,b):
    
    #초기값 설정
    #x0,y0
    before_x = 1
    before_y = 0
    
    #x1,y1
    x = 0
    y = 1
    
    #유클리드 알고리즘
    while b != 0:
        
        #미리 q = a//b를 구해놔야, b가 0일때 a//b를 하지 않는다
        q,r = a//b, a%b
        a,b = b,r
        
        #점화식에 의해 업데이트
        before_x,x = x, before_x - x*q
        before_y,y = y, before_y - y*q
    
    #b=0일때, x,y가 한번 더 업데이트 되어 before_x,before_y에 들어가므로
    return a,before_x,before_y

 

 

6. 다른 점화식

 

베주 항등식에 의하여, 적어도 하나가 0이 아닌 정수 a,b에 대해 ax + by = gcd(a,b)를 만족시키는 정수 x,y가 반드시 존재한다.

 

그러므로 $$ax + by = gcd(a,b)$$부터 시작해보자.

 

그런데, 유클리드 알고리즘에 의하여, gcd(a,b) = gcd(b, a%b)

 

그러므로, a = b, b = a%b를 대입하면...

 

$$bx_{1} + (a mod b)y_{1} = gcd(b,a mod b)$$

 

그런데, gcd(a,b) = gcd(b, a%b)이므로, $$bx_{1} + (a mod b)y_{1} = gcd(a,b) = ax + by$$

 

여기서 a%b는 a를 b로 나눈 나머지를 뜻하므로 다음과 같이 나타낼 수 있다.

 

$$ a = bq + a mod b$$

 

그러므로, $$a mod b= a - bq$$

 

이것을 대입하면, $$ax + by = bx_{1} + (a-bq)y_{1}$$

 

모든 a,b에 대해 성립하는 항등식이므로 우변을 a,b로 정리하면

 

$$ax + by = b(x_{1} - qy_{1}) + ay_{1} = ay_{1} + b(x_{1} - qy_{1})$$

 

그러므로, $$x = y_{1}$$와 $$y = (x_{1} - qy_{1})$$을 얻는다.

 

 

7 구현 예시 - 다른 점화식

 

위 알고리즘 그대로 구현해보면..

 

#재귀함수

def recursive_extended_gcd(a,b):
    
    #유클리드 알고리즘에서 a를 b로 나누는데, b가 0이면 종료함
    if b == 0:
        
        return a,1,0
    
    gcd,x1,y1 = recursive_extended_gcd(b,a%b)
    
    #점화식 x = y1, y = x-qy, q = a//b
    x = y1
    y = x1 - y1*(a//b)
    
    return gcd,x,y

 

 

재귀함수가 직관적?이긴 한데 반복문보다 조금 더 느리다

 

 

8. 연습문제

 

3955번: 캔디 분배 (acmicpc.net)

3955번: 캔디 분배

 

문제를 보면 결국 cx = ky + 1을 만족하는 x를 구하는 문제

 

 

9. 풀이

 

문제를 읽어보면, cx = ky + 1을 만족하는 x를 구하는 문제로 귀결된다.

 

베주항등식 형태로 바꿔보면 cx-ky = 1이다.

 

따라서 c,k에 대해 확장된 유클리드 알고리즘을 적용해서 gcd(c,k) = 1일때, 만족하는 정수해 x,y를 구해본다

 

def extended_gcd(a,b):
    
    before_x = 1
    before_y = 0
    
    x = 0
    y = 1
    
    while b != 0:
        
        q,r = a//b, a%b
        
        a,b = b,r
        
        before_x,x = x, before_x - x*q
        before_y,y = y, before_y - y*q
    
    return a,before_x,before_y

T = int(stdin.readline())

for t in range(1,T+1):
    
    k,c = map(int,stdin.readline().split())

    gcd,x,y = extended_gcd(c,k)

 

 

근데 이렇게 하면.. 예를 들어 c = 5, k = 10인 경우 gcd(c,k) = 5라서 cx-ky = 1을 만족하지 않는다

 

그러니까 최대공약수가 1이 아니라서 불가능한 형태다.

 

for t in range(1,T+1):
    
    k,c = map(int,stdin.readline().split())

    gcd,x,y = extended_gcd(c,k)
    
    if gcd == 1:
        
        print(x)
    
    else:
        
        print('IMPOSSIBLE')

 

 

그런데, 이렇게 하면 또 문제가 c=23, k=1337이면, x = -465, y = 8이 나온다

 

그런데, 이렇게 해도 베주 항등식은 물론 만족한다

 

$$23 \times (-465) + 1337 \times 8 = 1$$

 

그런데 사람이 사탕봉지를 음수개로 살수는 없잖아

 

그러면 불가능하다고 해야하나?

 

----------------------------------------------------------------------------------------------------------------------------------------

 

사실 베주 항등식을 만족하는 정수해 (x,y)는 유일하지 않다

 

$$ax + by = gcd(a,b)$$에 대해 좌변에 ab를 더하고 빼보면 다음과 같다

 

$$ax+ab + by-ab = a(x+b) + b(y-a) = gcd(a,b)$$

 

그러므로, (x,y)가 베주 항등식을 만족한다면, (x+b, y-a)도 베주 항등식을 만족하는 하나의 정수해이다.

 

--------------------------------------------------------------------------------------------------------------------------------------

 

이 문제에서, 우리는 $$cx - ky = 1$$을 만족하는 자연수 x,y를 찾아야한다.

 

바꿔말하면, $$cx + kt = 1$$을 만족하는 자연수 x, 음의 정수 t를 찾아야한다.

 

그런데 x = -465, y = 8은 x가 자연수가 아니고 y는 음의 정수가 아니잖아

 

그래서 $ax+ab + by-ab = a(x+b) + b(y-a) = gcd(a,b)$을 이용해서 또 다른 정수해를 찾는다

 

y가 음수가 될때까지 반복해서 x에 k를 더해주고, y에 c를 빼주면 될 것이다.

 

물론 그렇게 했는데 x가 $10^{9}$를 넘어가면 불가능한 해이므로(문제 조건에서 $10^{9}$개 넘어가는 사탕 봉지는 살 수 없다고 함) 제외해준다

 

from sys import stdin

def extended_gcd(a,b):
    
    before_x = 1
    before_y = 0
    
    x = 0
    y = 1
    
    while b != 0:
        
        q,r = a//b, a%b
        
        a,b = b,r
        
        before_x,x = x, before_x - x*q
        before_y,y = y, before_y - y*q
    
    return a,before_x,before_y

T = int(stdin.readline())

for t in range(1,T+1):
    
    k,c = map(int,stdin.readline().split())

    gcd,x,y = extended_gcd(c,k)

    if gcd == 1:
        
        if y >= 0:
            
            while y >= 0:

                x += k
                y -= c

        if x > (10**9):

            print('IMPOSSIBLE')

        else:

            print(x)
    
    else:
        
        print('IMPOSSIBLE')

 

참조

 

[알고리즘] 확장 유클리드 알고리즘 | 배하람 블로그 (baeharam.github.io)

[알고리즘] 확장 유클리드 알고리즘

 

 

Extended Euclidean algorithm - Wikipedia

Extended Euclidean algorithm - Wikipedia

 

예제로 알아보는 확장 유클리드 알고리즘 - 코딩 연습 (tistory.com)

예제로 알아보는 확장 유클리드 알고리즘

 

https://www.geeksforgeeks.org/euclidean-algorithms-basic-and-extended/

Euclidean algorithms (Basic and Extended) - GeeksforGeeks

 

베주 항등식 - 나무위키 (namu.wiki)

베주 항등식 - 나무위키

 

 

Extended Euclidean Algorithm | Algorithms, Blockchain and Cloud (helloacm.com)

Extended Euclidean Algorithm

 

 

Extended Euclidean Algorithm - Algorithms for Competitive Programming (cp-algorithms.com)

Extended Euclidean Algorithm - Algorithms for Competitive Programming