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

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

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

---

문제 풀이

페르마의 소정리

 

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

 

$(a \times Seed+c) \equiv X1 \;(mod \; m)$와 $(a \times X1+c) \equiv X2 \;(mod \; m)$를 빼서 한개의 연립합동방정식을 만든다.

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

 

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

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

그러면 양변에 $(Seed-X1)^{m-2}$를 곱해준다.

좌변은 $a(Seed-X1)^{m-1}$이 될 것이고 우변은 $(X1-X2) \times (Seed-X1)^{m-2}$가 될 것이다.

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

 

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

 

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

 

 

코드

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