마법 학교의 수정 에너지
실버 III의견: 0
마법 학교 '리세 아카데미'에서는 수정의 에너지를 \(a^b \bmod M\)으로 계산한다. 여기서 \(a\)는 수정의 기저 에너지, \(b\)는 증폭 횟수, \(M\)은 측정 한계치이다.
\(Q\)개의 수정이 있을 때, 각 수정의 에너지를 구하여라.
주의: \(b\)가 최대 \(10^{18}\)이므로 단순히 \(a\)를 \(b\)번 곱하면 시간 초과가 난다. 빠른 거듭제곱법(이진 거듭제곱)을 사용하여야 한다.
- \(1 \le Q \le 100\,000\)
- \(0 \le a \le 10^9\)
- \(0 \le b \le 10^{18}\)
- \(2 \le M \le 10^9\)
첫째 줄에 수정의 수 \(Q\)가 주어진다.
다음 \(Q\)개의 줄에 각 수정의 \(a\), \(b\), \(M\)이 공백으로 구분되어 주어진다.
\(Q\)개의 줄에 걸쳐 각 수정의 에너지 \(a^b \bmod M\)을 순서대로 출력한다.
3
2 10 1000
3 0 7
5 3 13
24
1
8
\(2^{10} = 1024\)이고 \(1024 \bmod 1000 = 24\)이다. \(3^0 = 1\)이고 \(1 \bmod 7 = 1\)이다. \(5^3 = 125\)이고 \(125 \bmod 13 = 8\)이다.
3
7 1 10
0 5 3
1 1000000000000000000 1000000007
7
0
1
\(7^1 = 7\)이고 \(7 \bmod 10 = 7\)이다. \(0^5 = 0\)이므로 \(0 \bmod 3 = 0\)이다. \(1^{10^{18}} = 1\)이고 \(1 \bmod 10^9+7 = 1\)이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
마법 학교의 수정 에너지
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
마법 학교의 수정 에너지