31478 포니 양은 놀고 싶어
문제
https://www.acmicpc.net/problem/31478
31478번: 포니 양은 놀고 싶어!
첫 번째 줄에 정수 $A$, $B$, $C$가 주어진다. ($1\leq A < 7$, $1\leq B, C \leq 10^{9}$, $B^C$는 $A$의 배수) 두 번째 줄에 정수 $K$와 $L$이 주어진다. ($0\leq K,L < 7$)
www.acmicpc.net
풀이
1. 분할정복 거듭제곱을 알아야한다.
x^y % R을 구할때 log(y)복잡도로 구할 수 있다.
2. 모듈러 역원을 알아야한다.
R이 소수일때
x^(R-2) % R = x^(-1) % R 이다.
이 두개만으로 후자는 구할 수 있다.
(B^C % R * A^(7-2) % R) % R 이다. 7은 소수기때문에 모듈러역원을 적용가능하다.
문제는 A이다.
지수가 B^C인걸 어떻게 처리하느냐가 관건인데...
모듈러 연산의 성질은 곱의 연산이 가능하단 것이다.
X = qm1 + r1, Y = qm2 + r2 (m1,m2는 몫, r1,r2는 나머지)
X*Y = q^2(m1+m2) + q(m1r2 + m2r1) + r1r2 = q(q(m1+m2) + m1r2 + m2r1) + r1r2
X*Y % q = r1r2 % R가 성립한다.
좋다! 제곱을 해도 해당 성질에 의해 나머지를 깔끔하게 구할 수 있다.
제곱을 한단 것은 같은수를 계속 곱해준단 것이고, 나머지는 순환할 것이다.
A의 범위가 적으므로 직접 다 구할 수 있다.
(만약 A의 범위가 크다면, 각 수마다 순환하는 범위를 구하고, 최소공배수 때리면 된다.)
| A\승 | 0 | 1 | 2 | 3 | 4 | 5 |
| 1 | 1 | ... | ||||
| 2 | 1 | 2 | 4 | ... | ||
| 3 | 1 | 3 | 2 | 6 | 4 | 5 |
| 4 | 1 | 4 | 2 | ... | ||
| 5 | 1 | 5 | 4 | 6 | 2 | 3 |
| 6 | 1 | 6 | ... |
직접 구해보면 나머지는 이렇게 순환한다.
즉 A^(B^C) % 7 = A^(B^C%6) % 7을 구하면 된다.