[BOJ/PYTHON] 14565. 역원(Inverse) 구하기

백준 문제 링크: https://www.acmicpc.net/problem/14565

문제 요약

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

덧셈역: (a+b) mod n = 0일 경우의 b는 a의 덧셈역

곱셈역: (a*c) mod n = 1이면 c는 a의 곱셈역

핵심 아이디어

덧셈역: b = -a % n

곱셈역: a * c = nx + 1

곱셈역: ac - nx = 1 => ax0 - ny0 = 1

확장 유클리드 호제법을 이용한 풀이이다.

풀이

# gold2-14565. 역원(Inverse) 구하기

import sys
input = sys.stdin.readline

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

def solve():
    x0, y0, value0 = 0, -1, n
    x1, y1, value1 = 1, 0, a

    while value1 != 0:
        quotient = value0 // value1
        x0 -= x1 * quotient
        y0 -= y1 * quotient
        value0 -= value1 * quotient

        x0, x1 = x1, x0
        y0, y1 = y1, y0
        value0, value1 = value1, value0

    if value0 == 1:
        return x0 % n
    else: 
        return -1

multiplicative_inverse = solve()
additive_inverse = -a % n

print(additive_inverse, multiplicative_inverse)

실행 시간

메모리 31256KB, 시간 40ms (python3)