[BOJ][Python] 백준 20412번 - 추첨상 사수 대작전! (Hard)

BOJ

[BOJ][Python] 백준 20412번 - 추첨상 사수 대작전! (Hard)

송댕 2022. 7. 2. 08:23

728x90

문제 링크: https://www.acmicpc.net/problem/20412

20412번: 추첨상 사수 대작전! (Hard)

한 줄에 걸쳐 준표가 좋아하는 소수 m, 참가자들이 정한 Seed, 시연으로 공개된 X1, X2 이 주어진다. 항상 가능한 상황만 입력으로 주어진다.

www.acmicpc.net

문제 풀이

페르마의 소정리

페르마의 소정리를 이용하여 풀었다.

$(a \times S e e d + c) \equiv X 1 (m o d m)$ 와 $(a \times X 1 + c) \equiv X 2 (m o d m)$ 를 빼서 한개의 연립합동방정식을 만든다.

$a (S e e d - X 1) \equiv X 1 - X 2 (m o d m)$ 가 되는데 m은 소수이고 0 < Seed, X1, X2 < m라고 명시되어 있으므로 Seed-X1 < m이고, m은 소수이기 때문에 양의 배수가 존재할 수 없다. 따라서 Seed-X1과 m은 서로소이며 즉, 페르마의 소정리를 이용할 수 있다.

여기서 페르마의 소정리를 간단하게 얘기하자면 p와 m은 서로소이고 m이 소수면 $p^{m - 1} \equiv 1 (m o d m)$ 을 만족한다.

다시 위의 식으로 돌아와보자. 우리가 구해야 하는건 a와 c이고 $a (S e e d - X 1) \equiv X 1 - X 2 (m o d m)$ 의 식에서 m,Seed, X1, X2는 입력으로 주어지므로 (Seed-X1)의 값은 알고 있다. 또한 X1-X2의 값도 알고 있다.

그러면 양변에 $(S e e d - X 1)^{m - 2}$ 를 곱해준다.

좌변은 $a (S e e d - X 1)^{m - 1}$ 이 될 것이고 우변은 $(X 1 - X 2) \times (S e e d - X 1)^{m - 2}$ 가 될 것이다.

이때 위에서 얘기한 Seed-X1과 m은 서로소, m은 소수, $p^{m - 1} \equiv 1 (m o d m)$ 를 이용하면 $(S e e d - X 1)^{m - 1} \equiv 1 (m o d m)$ 가 되고 이 식을 이용한다.

정리하면 $a (S e e d - X 1)^{m - 1} \equiv (X 1 - X 2) \times (S e e d - X 1)^{m - 2} (m o d m)$ 은 $a \equiv (X 1 - X 2) \times (S e e d - X 1)^{m - 2} (m o d m)$ 가 된다. 뒤의 연산은 분할 정복을 이용한 거듭제곱을 이용하면 빠르게 구할 수 있다.

이제 a를 구했다면 c는 X1 = (a × Seed + c) % m 식에서 $c \equiv X 1 - (a \times S e e d) (m o d m)$ 로 변형하여 c를 구할 수 있다.

코드

	m, seed, x1, x2 = map(int, input().split())
	ans, sq = 1, seed-x1
	for i in reversed(bin(m-2)[2:]):
	if i == '1':
	ans = (ans*sq)%m
	sq = (sq*sq)%m
	a = (ans*(x1-x2))%m
	c = (x1-(a*seed))%m
	print(a, c)

view raw 20412.py hosted with ❤ by GitHub

여담으로 이 코드는 가장 처음에 풀은 코드를 업로드 했는데 pow 함수에서 pow(a, b, m)을 이용하면 a^b%m을 알아서 분할 정복해서 값을 내어준다. 그 외에 자잘한 공백들을 없애서 76B로 정답을 맞췄다.

728x90

저작자표시 비영리 동일조건 (새창열림)