[Python] 31478번 포니 양은 놀고 싶어!

https://www.acmicpc.net/problem/31478

31478번: 포니 양은 놀고 싶어!

---

 

24/04/15

 

 

간단한 정수론 문제입니다. 분할 정복을 이용한 거듭제곱에 관한 지식과, 페르마의 소정리에 관한 지식이 있어야 해결할 수 있습니다.

---

 

문제 접근 방식:

 

 

결국 $A^{B^C}$와 $B^C / A$를 빨리 구하는 문제로 귀결됩니다.

 

후자는 빠르게 구할 수 있습니다. 결국 $7$일이라는 범위 안에서만 따지는 것이기 때문에 $7$에 대한 모듈로 연산을 취해주는 것이고, $7$은 소수이기 때문에 $A$가 어떤 값이든 간에 모듈로 역원을 구할 수 있습니다.

 

파이썬에서는 모듈로 역원을 pow함수를 통해 간단하게 구할 수 있습니다.

 

pow(value, power, mod)에서, power인자를 $-1$로 넘겨주기만 하면 됩니다.

 

$A^{B^C}$의 mod $7$값은 $A^{B^C \textrm{ mod } 7} \textrm{ mod }7$이 아님을 주의합시다.

 

페르마의 소정리에 의하면, $n$과 $A$가 서로소일때, $A^{\phi(n)} \equiv 1 (\textrm{mod }n)$가 성립함을 알고 있습니다.

 

이를 이용해봅시다. 우리는 $n=7$일때의 경우를 따지고 있습니다. $n$이 소수이고, $A$는 $7$보다 작으므로, $A$의 값과 관계 없이 서로소입니다.

 

$B^C$의 값이 어느 정도로 큰 지는 잘 모르지만, 이 값을 $k$라고 한다면, 우리는 $A^k \textrm{ mod }7$의 값을 구하는 것과 같습니다.

 

우리는 $\phi(7) = 6$임을 알고 있으므로, $A^6 \equiv 1 \textrm { mod }7$임을 알고 있습니다.

 

이를 이용하면, $A^k$를 $A^6$들의 곱으로 분해할 수 있습니다. 즉, 다음과 같습니다.

 

$$\begin{align} A^k \equiv A^{6}\cdot A^{6}\cdot \dots \cdot A^{k \text{ mod }6} \\ \equiv 1 \cdot 1\cdot\dots \cdot A^{k \text{ mod }6} \\ \equiv A^{k \text{ mod }6} \text{ mod }7 \end{align} $$

 

따라서, $B^C$를 $6$으로 나눈 나머지를 구하고 이를 $p$라고 하면, $A^p$를 $7$로 나눈 나머지가 답이 됩니다.

 

이는 파이썬의 pow함수로 쉽게 구현할 수 있습니다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 31478번 포니 양은 놀고 싶어!
# 분할 정복을 이용한 거듭 제곱, 모듈로 역원, 정수론, 오일러파이함수
A, B, C = map(int, input().split())
K, L = map(int, input().split())
p, q = pow(A, pow(B, C, 6), 7), (pow(B, C, 7)*pow(A, -1, 7))%7
if (K+p)%7 == (K+q)%7 == L:
    print(3)
elif (K+p)%7 == L:
    print(1)
elif (K+q)%7 == L:
    print(2)
else:
    print(0)