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
code tham khảo
Nè :
Python
def modular_exponentiation(a, b, mod):
result = 1
a %= mod
while b > 0:
if b % 2 == 1:
result = (result * a) % mod
b //= 2
a = (a * a) % mod
return result
n = int(input())
for _ in range(n):
a, b = map(int, input().split())
print(modular_exponentiation(a, b, 10**9 + 7))
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!