DCT03 – Lũy thừa chia đôi
Xem dạng PDF
Mã bài:
dct03
Điểm:
1 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
512M
Dữ liệu vào:
stdin
Dữ liệu ra:
stdout
Tác giả:
Dạng bài
Đề bài
Cho hai số nguyên không âm a, n. Tính a^n modulo 1000000007.
Giá trị n có thể rất lớn, vì vậy cách nhân a liên tiếp n lần không đáp ứng thời gian. Hãy khai thác bài toán con với số mũ n/2.
Dữ liệu vào
Một dòng gồm hai số nguyên không âm a và n.
Dữ liệu ra
In ra phần dư của a^n khi chia cho 1000000007.
Ràng buộc
0 ≤ a,n ≤ 10^18. Quy ước 0^0 = 1.
Ví dụ
Ví dụ 1
Input
2 10
Output
1024
Giải thích: 2^10 = 1024.
Ví dụ 2
Input
3 13
Output
1594323
Giải thích: 3^13 = 1594323.
Bình luận