[백준/14565] 역원(Inverse) 구하기 | 확장 유클리드 알고리즘 | 덧셈역,곱셈역

확장 유클리드 알고리즘

유클리드 알고리즘에서는 나누는 값, 나머지로 r = 0일 때까지의 b값을 통해 최대공약수를 구했다. 확장 유클리드 알고리즘은 이를 활용하여 ax + by = gcd(a,b)가 존재하는 선형 방정식을 푸는 문제다.

 

지금까지 이런 식으로 유클리드 알고리즘을 통해 최대공약수를 구했다면

다음과 같이 x, y 값을 통해 gcd 값과 선형방정식의 정수해를 구할 수 있다.

이 문제에서 구하고자하는 곱셈역은 결국 (a*c) % n = 1을 찾는 문제인데, 물론 주어진 a와 n을 활용하여 1부터 n까지의 연산을 통해서 구할 수도 있다. 하지만 n의 범위는 10**12로 더 효율적인 방법인 확장 유클리드 알고리즘으로 해를 구하는 방법이 분명히 존재한다.

 

이 문제에서는 xgcd(11*x, 26)=1이 되는 x를 찾는 것이다. 따라서 확장 유클리드 알고리즘을 활용하여 11 * x + 26 * y = 1일 때의 x 값을 구하면 곱셈역의 해를 찾을 수 있다. 

 

여기서 주의해야 할 점은 x 값이 음수가 나올 때다. 예를 들어 a = 6, n = 13일 때 a의 역원은 11이지만 이를 확장 유클리드 알고리즘으로 구해보면 -2값이 나온다. 

💡 모듈러 연산

모듈러 연산은 결과 값에 n을 아무리 더해도 결국 같은 값을 도출한다는 이론이다

따라서 정확한 값을 구하기 위해 x 값이 음수가 도출되었을 때, 우리는 n을 더해가면서 x 값을 도출한다.

---

전체 코드

import sys
input = sys.stdin.readline

n, a = map(int, input().split())

# 덧셈역 구하기
# (a+b)%n = 0이기 위해서 b = n-a가 되어야함.

# 곱셈역 구하기
# (a*c)%n = 0 

# 재귀로 gcd 구하기
def gcd(a,b):
    if b == 0 : return a
    return gcd(b, a%b)

def xgcd(a,b):
    r1, r2 = a, b
    s1, s2 = 1, 0
    t1, t2 = 0, 1
    
    while True:
        # 확장 유클리드 알고리즘 활용
        q = r1 // r2
        r = r1 - (q*r2)
        s = s1 - (q*s2)
        t = t1 - (q*t2)
                
        if r == 0 : return s2

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

if gcd(a,n) != 1 : 
    m = -1
    
else:
    m = xgcd(a,n)
    while m <= 0:
        m += n
        
print(n-a, m)