Tính lũy thừa 1 - LCOJ: Luyen Code Online

POWER1 - Tính lũy thừa 1

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Tác giả:

Hieu Nguyen

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

Problem source: Chuyên Sơn La Online Judge

Bình luận

Hãy đọc nội quy trước khi bình luận.

1

dinhvantung0611 đã bình luận lúc 14, Tháng 3, 2024, 16:15

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

3

dungolduck đã bình luận lúc 8, Tháng 2, 2024, 7:17

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

def power(base, exponent, modulus):

result = 1

Giảm kích thước của base nếu cần thiết

base = base % modulus 


while exponent > 0:
    # Nếu exponent là số lẻ, thì nhân vào kết quả
    if exponent % 2 == 1:
        result = (result * base) % modulus

    # Chia giảm bài toán thành exponent/2
    base = (base * base) % modulus
    exponent //= 2

return result

mod = 10**9 + 7 a, n = map(int, input().split())

result = power(a, n, mod) print(result)

-1

tungkq123 đã bình luận lúc 8, Tháng 5, 2024, 9:07

nên hạn chế để code phần cmt bn nhé

1

phongnguyen19811 đã bình luận lúc 1, Tháng 10, 2023, 1:16

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.

0

vuonghao đã bình luận lúc 20, Tháng 9, 2023, 10:07

Nhờ các bạn AC giùm Test cuối với. Mình bị TLE

0

Lionel_Nguyen đã bình luận lúc 15, Tháng 11, 2023, 16:11

dùng lũy thừa nhị phân là AC