문제 설명
문제
집합 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을 출력한다.
'알고리즘 > 백준' 카테고리의 다른 글
[백준 / 그래프] 20040 : 사이클 게임 (python) (2) | 2024.04.10 |
---|---|
[백준 / 그래프] 1717 : 집합의 표현 (python) (0) | 2024.04.10 |
[백준 / 정수론] 11689 : GCD(n, k) = 1 (python) (0) | 2024.04.08 |
[백준 / 정수론] 2609 : 최대공약수와 최소공배수 (python) (0) | 2024.04.08 |
[백준 / 정수론] 1978 : 소수 찾기 (python) (0) | 2024.04.08 |