POWER1 - Tính lũy thừa 1
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Cho hai số nguyên dương ~a~ và ~n~. Tính ~a^n~.
Input
- Gồm một dòng duy nhất ghi hai số nguyên dương ~a~ và ~n~ cách nhau bởi dấu cách.
Giới hạn:
- ~1 ≤ a, n ≤ 10^9~.
Output
- Phần dư của phép tính ~a^n~ chia cho ~10^9 + 7~.
Sample
Input #1
5 7
Output #1
78125
Problem source: Chuyên Sơn La Online Judge
Bình luận
Nếu bạn sử dụng C++. Sẽ cần kiến thức về luỹ thừa nhị phân và phép nhân Ấn Độ, nếu bạn chưa có kiến thức về 2 kỹ thuật này thì có thể tham khảo thêm (mình để link bài viết ở đây)
https://viblo.asia/p/phep-nhan-an-do-thuat-toan-binh-phuong-va-nhan-gDVK2dmrlLj
các bạn tham khảo phép tính dư module kết hợp với lũy thừa nhị phân là đc
Var x,y:int64; Function LUTH(a,b:int64):int64; Var k,h:int64; Begin If b = 1 then exit(a mod 1000000007); k:=b div 2; h:=a*a mod 1000000007; If b mod 2 = 0 then exit(LUTH(h,k) mod 1000000007) Else exit((LUTH(h,k) mod 1000000007) * a mod 1000000007); End; Begin Read(x,y); Write(LUTH(x,y)); Readln; End.
Nhờ các bạn AC giùm Test cuối với. Mình bị TLE
dùng lũy thừa nhị phân là AC