14565번: 역원(Inverse) 구하기 집합 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의 www.acmicpc.net 분석 덧셈역 n-a (11 + 15) mod 26 = 0 곱셈역 xgcd(11﹡X, 26) = 1이 되는 X를 찾는 것 ➔ 11 * 𝒔 + 26 * 𝒕 = 1일 때 𝑆 값(곱셈역) (11 * 19) mod 26 = 1 확장 유클리드 알고리즘 확장 유클리드 호제법 유클리드 호제법 : 두 수의 최대 공약수 구하기 확장 유클리드 호제법 : 방정식의 해 구하기 베주 항등식 (Bezout's..