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
MOD = 10**9
def power_mod(a, b, mod):
if a == 0 and b == 0:
return 1
result = 1
a = a % mod
while b > 0:
if b % 2 == 1:
result = (result * a) % mod
a = (a * a) % mod
b //= 2
return result
n = int(input().strip())
queries = [tuple(map(int, input().strip().split())) for _ in range(n)]
results = []
for a, b in queries:
value = (power_mod(a, b, MOD) + 7) % MOD
results.append(value)
print("\n".join(map(str, results)))
sai cho nao vay
7 bình luận nữa