[백준 / 정수론] 14565 : 역원(Inverse) 구하기 (python)

문제 설명

문제

집합 Zn을 0부터 n-1까지의 정수 집합이라고 하자. Zn ∋ a, b, c 일 때, (a+b) mod n = 0이면 b는 a의 덧셈역이라고 하고 (a*c) mod n = 1이면 c는 a의 곱셈역이라고 한다.

정수 N, A가 주어졌을 때 Zn에서의 A의 덧셈역과 곱셈역을 구하시오.

단, 곱셈역을 구할 수 없으면 -1을 출력한다.

입력

첫 번째 줄에 N(2 ≤ N ≤ 10^12)과 A(1 ≤ A < N)이 주어진다.

출력

첫 번째 줄에 A의 N에 대한 덧셈역과 곱셈역을 한 줄에 공백으로 구분하여 출력한다.

예제 입력 1

26 11

예제 출력 1

15 19

예제 입력 2

100 20

예제 출력 2

80 -1

예제 입력 3

32760247633 22801763489

예제 출력 3

9958484144 12390598440

힌트

• 덧셈역 (11 + 15) mod 26 = 0
• 곱셈역 (11 * 19) mod 26 = 1

 

풀이

# 유클리드 호제법
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)

# 확장 유클리드 호제법
def extend(a, b):
    sol = [0] * 2
    if b == 0:
        sol[0] = 1
        sol[1] = 0
        return sol
    q = a // b
    v = extend(b, a%b)
    sol[0] = v[1]
    sol[1] = v[0] - v[1] * q
    return sol

N, A = map(int, input().split())
print(N - A, end = ' ') # 덧셈역
if gcd(A, N) != 1:
    c = -1
else:
    c = extend(A, N)[0]
    while c <= 0:
        c += N
print(c) # 곱셈역

 

예제 1을 기준으로 N = 26, A = 11이다.

 

# 덧셈역

덧셈역은 (11 + b) % 26 = 0 이기 때문에 11 + b = 26*x면 된다. A < N 이라는 조건이 있으므로 11 + b가 26도 되기 때문에 'N - A = 덧셈역' 임을 알 수 있다.

 

# 곱셈역

(11 * c) % 26 = 1 의 식을 통해 11 * c와 26이 서로소임을 알 수 있다. 서로소는 확장 유클리드 호제법을 이용하면 쉽게 구할 수 있다.

확장 유클리드 호제법은 ax + by = c 일 때, c는 a와 b의 최대공약수의 배수임을 증명한다.(a와 b는 정수) 따라서 ax + by = GCD(a, b) 이다. 서로소는 GCD(a, b) = 1을 의미하므로 ax + by = 1의 식을 세울 수 있다.

예제 1에 적용하면, 11x + 26y = 1이 되고, 이때 x를 구하면(c) 곱셈역을 알 수 있다.

곱셈역이 음수가 나오는 경우도 존재하는데, 이때는 x에 N을 더해서 양수로 만들어주면 된다. 모듈러 연산에서는 결과 값에 N을 아무리 더해도 결국 같은 값을 도출한다.

 

+ GCD(a, b) = 1이 아닐 경우 서로소가 아니며 곱셈역을 구할 수 없다. 따라서 -1을 출력한다.