[알고리즘 문제 풀이][확장유클리드] 백준 14565번 - 역원(Inverse) 구하기

백준 14565번 역원(Inverse) 구하기 문제입니다.

(유클리드 호제법 + 확장된 유클리드 호제법 문제 Extended Euclidean Algorithm)

 

※ 본 게시글에는 확장된 유클리드 호제법의 원리에 대한 설명은 포함되어있지 않습니다. 문제 풀이에 대한 내용만 정리되어있습니다.

 

- 문제 설명: https://www.acmicpc.net/problem/14565

- 문제 풀이:

 

본 문제는 덧셈역과 곱셈역을 출력하는 문제입니다.

 

(1) 덧셈역

(a+b) mod n = 0 이 나오는데, 첫번째 입력인 N 26과 A 11을 넣어보면 (11 + b) mod 26 = 0 이 나오는 것을 찾는 것입니다. 그러면 당연히 26 % 26 을 하면 0이 나오므로 b는 26 - 11 로 쉽게 15를 구할 수 있습니다. 또한 주어진 입력 조건에서 1<= A < N 조건이 있으므로 무조건 N - A를 출력하면 덧셈역은 구할 수 있습니다.

 

(2) 곱셈역

(a*c) mod n = 1인 경우 곱셈역이라고 합니다. 주어진 첫 번째 입력에 따르면 (11 * c) mod 26 = 1 입니다. 곱셈역을 1부터 N까지 해보면서 일일히 mod 한 값이 1이 나오는지 확인하는 방법도 있겠지만, 확장된 유클리드 호제법을 이용하면 빠르게 곱셈역을 구할 수 있습니다. 위키 백과에 따르면 아래와 같은 설명도 있습니다.

특히, m, n이 서로소 (gcd(m,n) = 1)인 경우 유용한데, 그럼 위의 식은 am + bn = 1이 되고, 여기서 a는 모듈로 연산의 곱의 역원(modular multiplicative inverse)이 되기 때문이다.

[출처] https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95#%ED%98%B8%EC%A0%9C%EB%B2%95%EC%9D%98_%ED%99%95%EC%9E%A5

 

본 문제를 풀기 위해서는 유클리드 알고리즘을 먼저 알아야합니다. 이를 먼저 확인한 후에 (https://computer-choco.tistory.com/454), 확장된 유클리드 알고리즘을 보아야합니다. 유클리드 알고리즘은 gcd(a, b) 를 넣었을 때 a와 b의 최대 공약수를 찾아주는 방법입니다. 예를 들어 12와 4라면 이 둘의 최대공약수 (gcd) 는 4일 것이고, gcd(12, 4) 를 넣으면 답은 4가 나오게 됩니다.

 

확장된 유클리드 알고리즘은 두 개의 수, a와 b에 어떤 정수를 곱한 다음에 더해야 최대공약수가 나오는지를 알려줍니다.

a * s + b * t = gcd

를 찾아주는 것입니다.

a는 12이고, b는 4일 때, 최대 공약수 (gcd) 는 4가 되므로, 12 * s + 4 * t = 4 를 찾는 식이 됩니다. 그러면 확장된 유클리드 알고리즘 이용시 12 * 0 + 4 * 1 = 4 가 나오게 됩니다.

 

확장된 유클리드 알고리즘의 방법을 본 게시물에서는 설명하지 않으므로, 설명 및 코드가 필요하신 분들은 아래를 참고하시면 됩니다.

[확장된 유클리드 알고리즘 1] https://kbw1101.tistory.com/53?category=778980
[확장된 유클리드 알고리즘 2] https://ssungkang.tistory.com/entry/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EA%B3%BC-%ED%99%95%EC%9E%A5%EB%90%9C-%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

 

그러면 위 코드들을 참고하여 xgcd 함수를 구현하면 됩니다.

본 문제에서는 xgcd (11*x, 26) = 1 이 되는 x 를 찾는 것이므로, 11 * s + 26 * t = 1일 때 s 값을 구하면 그것이 바로 답 (곱셈역)이 될 것 입니다. (위에서 인용한 위키백과의 설명은 이를 의미합니다.)

 

그런데, xgcd 를 이용하여 s 값을 구했을 때 s가 항상 양수가 나오는 것은 아닙니다.

실제로 구해보면 s는 -7, t는 3이 나올 것입니다.

11 * (-7) + 26 * 3 = 1 이 성립하기 때문입니다.

 

그럴 땐 s값 (-7) 에 26 씩 더해가면서 양수가 되게 만들면 됩니다.

실제 식으로 보면 다음과 같습니다.

 

11 * (-7 + 26 - 26) + 26 * 3 = 1 로 바꿀 수 있고,

11 * (19 - 26) + 26 * 3 = 1

11 * 19 + 26 * (-11 + 3) = 1

11 * 19 + 26 * (-8) = 1 로 변형이 가능합니다.

 

※ 모듈러 연산은 결과 값에 N을 아무리 많이 더해도 결국 같은 값을 얻는다는 설명:

https://kau-algorithm.tistory.com/36

 

여기까지 구하면 덧셈역과, 곱셈역을 출력할 수 있게 됩니다.

 

(3) 출력시 주의 사항

본 문제에서는 풀이시 주의사항이 있는데, 곱셈역을 구할 수 없는 경우 -1을 출력하라는 조건이 있는 것입니다. 곱셈역이 없다는 것은 A*s 와 N 이 서로소가 아니라는 것을 의미합니다.

gcd (A, N) 을 이용하여 최대공약수가 1이 나오는 것이 맞는지 확인이 필요합니다.

그래서 이 문제를 풀기 위해서는 유클리드 알고리즘의 선행이 필요합니다.

 

※ 정확한 증명 및 해설 찾지 못함, 업데이트 필요

- 코드: 

def gcd(a, b):
    return gcd(b, a%b) if b else a

def xgcd(a, b):
    r1 = a
    r2 = b
    s1 = 1
    s2 = 0
    t1 = 0
    t2 = 1

    while True:
        q = r1 // r2
        r = r1 - (q * r2)
        s = s1 - (q * s2)
        t = t1 - (q * t2)

        if r == 0:
            # gcd: r2, s: s2, t: t2
            return s2 # inverse of multiply

        r1 = r2
        r2 = r
        s1 = s2
        s2 = s
        t1 = t2
        t2 = t

N, A = map(int, input().split())

if gcd(A, N) != 1:
    inv = -1
else:
    inv = xgcd(A, N)
    while inv <= 0:
        inv += N

print(N-A, inv)

xgcd 함수의 리턴 값을 문제에서 곱셈역을 위해 구해야하는 s2로 출력하였습니다.

 

- 실수 포인트 & 반례:

본 문제는 아직 반례가 없습니다.