8057 : 빠른 거듭제곱 II
•시간제한: 3.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
세 정수 $a, b, c$가 주어질 때, $a^{b^c} \pmod{10^9+7}$의 값을 구하는 프로그램을 작성하십시오.
단, $0^0 = 1$로 정의합니다.
[제약 조건]
• $1 \le n \le 100{,}000$
• $0 \le a, b, c \le 10^9$
단, $0^0 = 1$로 정의합니다.
[제약 조건]
• $1 \le n \le 100{,}000$
• $0 \le a, b, c \le 10^9$
입력 설명
첫째 줄에 테스트 케이스(질의)의 개수 $n$이 주어집니다. ($1 \le n \le 100{,}000$)
다음 $n$개의 줄에 걸쳐 세 정수 $a, b, c$가 공백으로 구분되어 주어집니다. ($0 \le a, b, c \le 10^9$)
다음 $n$개의 줄에 걸쳐 세 정수 $a, b, c$가 공백으로 구분되어 주어집니다. ($0 \le a, b, c \le 10^9$)
출력 설명
각 질의에 대해 $a^{b^c} \pmod{10^9+7}$의 결과를 한 줄에 하나씩 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3
3 7 2
2 3 0
10 2 3
출력 예시
COPY
복사되었습니다!
복사되었습니다!
742188145
2
100000000도움
페르마의 소정리 $a^{p-1} \equiv 1 \pmod p$에 의해, 지수 부분인 $b^c$에 소수 $p = 10^9+7$보다 $1$이 작은 $p-1 = 10^9+6$을 법(Modulo)으로 취할 수 있습니다. 즉, $b^c \pmod{10^9+6}$을 먼저 구한 뒤 이를 지수로 적용하여 거듭제곱을 수행합니다.