CSES - Exponentiation | Lũy thừa
Xem PDF
Điểm:
1300 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Hãy tính toán các giá trị \(a^b \mod 10^9\) \(+ 7\) một cách hiệu quả.
Lưu ý: Trong bài này, ta giả định rằng \(0^0 = 1\).
Input
- Dòng đầu tiên chứa một số nguyên \(n:\) số lượng câu hỏi.
- Sau đó là \(n\) dòng, mỗi dòng chứa hai số \(a,b\).
Output
- In ra các giá trị \(a^b \mod 10^9\) \(+\) \(7\).
Constraints
- \(1 \leq n \leq 2 \cdot 10^5\)
- \(0 \leq a, b \leq 10^9\)
Example
Sample input
3
3 4
2 8
123 123
Sample output
81
256
921450052
Bình luận
PYTHON Mãi đỉnh:
MOD = 10**9 + 7
def powmod(a, b):
kq = 1
while b > 0:
if b % 2 == 1:
kq = (kq * a) % MOD
a = (a * a) % MOD
b //= 2
return kq
def main():
import sys
input = sys.stdin.read
data = input().split()
n = int(data[0])
index = 1
results = []
for _ in range(n):
a = int(data[index])
b = int(data[index + 1])
result = powmod(a, b)
results.append(result)
index += 2
if name == "main":
main()
Gợi ý: dùng lũy thừa nhị phân + mod
Code C++: https://ideone.com/rNpdsf
Python AC kiểu chi rứa mọi người 🙁
Hãy tính toán các giá trị \(a^b \space\) \(mod\) \(\space 10^9 +7\) một cách hiệu quả.
Lưu ý: trong bài này, ta giả định rằng \(0^0 = 1\).
Input
Output
Constraints
Example
Test
Input
Output
Note
memory 512K chắc là hơi bé đó ad ơi!