BOJ 14565 역원 구하기 · noir1458's blog

문제

BOJ 14565 역원 구하기
정수 $N, A$ 가 주어졌을 때, 집합 $Z_N = \{0, 1, \dots, N-1\}$ 에서 다음을 구하는 문제다.

덧셈에 대한 역원 $b$ : $(A+b) \bmod N = 0$
곱셈에 대한 역원 $c$ : $(A \cdot c) \bmod N = 1$

단, 곱셈 역원은 항상 존재하지 않을 수 있으므로, 존재하지 않으면 $-1$ 을 출력해야 한다. 제약이 커서 $N \le 10^{12}$ 이므로 단순 탐색은 불가능하다.

복잡도 분석

Time Complexity: $O(\log N)$
확장 유클리드 알고리즘 1회로 최대공약수와 계수를 함께 구한다.
Space Complexity: $O(\log N)$
재귀 구현 기준 호출 스택을 포함한 공간 복잡도. 반복문으로 구현하면 $O(1)$ 까지 줄일 수 있다.

접근법

1. 덧셈 역원

$A < N$ 이므로 가장 자연스럽게 다음이 성립하도록 잡는다. $A + b = N$ 따라서 덧셈 역원 $b$ 는 다음과 같다. $b = N - A$

2. 곱셈 역원의 존재 조건

우리가 원하는 것은 $Ax \equiv 1 \pmod N$ 이다. 이를 정수식으로 바꾸면 다음과 같은 부정 방정식의 정수해 $x, y$ 가 존재해야 한다. $Ax + Ny = 1$ 베주 항등식에 의해 $Ax + Ny = \gcd(A, N)$ 꼴의 해는 항상 존재하므로, 우변이 $1$ 이 되려면 반드시 ** $\gcd(A, N) = 1$ **이어야 한다. 즉, $A$ 와 $N$ 이 서로소일 때만 곱셈 역원이 존재한다.

3. 확장 유클리드 알고리즘

확장 유클리드 알고리즘은 $ax + by = \gcd(a, b)$ 를 만족하는 $x, y$ 를 함께 구해준다. 재귀적으로 $\text{egcd}(a, b) \to \text{egcd}(b, a \bmod b)$ 를 호출한다. 만약 아래 단계에서 $bx_1 + (a \bmod b)y_1 = g$ 를 알고 있다면, $a \bmod b = a - \lfloor a/b \rfloor b$ 를 대입하여 다음을 얻는다. $ay_1 + b(x_1 - \lfloor a/b \rfloor y_1) = g$ 따라서 현재 단계의 계수는 다음과 같다. $x = y_1, \qquad y = x_1 - \lfloor a/b \rfloor y_1$

4. 결과의 정규화

확장 유클리드로 얻은 $x$ 는 음수일 수 있다. 문제에서 원하는 역원은 $Z_N = \{0, \dots, N-1\}$ 안의 원소이므로, 최종 답은 $x \bmod N$ 으로 정규화하여 출력해야 한다.

흐름 정리

핵심 아이디어 요약

덧셈 역원은 $N - A$
곱셈 역원은 $\gcd(A, N) = 1$ 일 때만 존재
확장 유클리드로 $Ax + Ny = 1$ 의 해를 구하고 $x \bmod N$ 을 출력

풀이

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

rev_sum = N - A

def egcd(a, b):
    if b == 0:
        return (a, 1, 0)

    g, x1, y1 = egcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return (g, x, y)

g, x, y = egcd(A, N)

rev_mul = -1
if g == 1:
    rev_mul = x % N

print(rev_sum, rev_mul)

Code Review

함수 내부에서 외부 변수 의존성을 줄여 깔끔하게 구현되었다.
rev_sum, rev_mul과 같이 변수명을 통해 의미를 명확히 전달했다.
$N$ 의 범위가 크지만 $\log N$ 알고리즘이므로 파이썬으로도 충분히 통과 가능하다.
C++로 구현할 경우 $10^{12}$ 범위를 수용하기 위해 반드시 long long을 사용해야 한다.

유사 문제 추천

최대공약수와 최소공배수 (BOJ 2609)
GCD(n, k) = 1 (BOJ 11689)
서로소 (BOJ 4355)
조합 (BOJ 13977) - 모듈러 역원을 활용한 조합 계산

문제