Lũy thừa mod
Xem PDF
Điểm:
250 (p)
Thời gian:
2.0s
Bộ nhớ:
640M
Input:
bàn phím
Output:
màn hình
Tính: \(a^{b^c}\) \(mod\) \(10^{18} + 9\).
Input
- Dòng đầu ghi \(Q\) không quá \(5000\) - số câu hỏi.
- \(Q\) dòng tiếp theo mỗi dòng ghi 3 số \(a,b,c\) không quá \(10^{15}\).
Output
- Ứng với mỗi testcase, in ra đáp án cần tìm.
Example
Test 1
Input
3
2 3 2
5 2 2
3 4 5Output
512
625
824168097938645257
Bình luận
Tìm hiểu về định lí fermat nhỏ
-
0
huyhau6a2
8:42 a.m. 21 Tháng 12, 2021
←
đã chỉnh sửa
→
-
8
tknhannguyenphu
9:41 a.m. 21 Tháng 12, 2021
-
0
huyhau6a2
1:11 p.m. 21 Tháng 12, 2021
-
0
huyhau6a2
11:41 a.m. 21 Tháng 12, 2021
←
đã chỉnh sửa
→
6 bình luận nữahmm khó đấy mình đọc cả fermat với euler mà vẫn chả hiểu liên quan gì đến bài này hết hmm
a^(n - 1) mod n = 1
-> a^[(n - 1).k] mod n = 1
-> a ^ [(n - 1).k + r] mod n = a^[(n - 1).k] * a^r mod n = a^r mod n
->a^(b^c) mod n = a^[b^c mod (n - 1)] mod n
Cảm ơn bạn mình ac 600ms rồi nha
Vỗ tay vỗ tay