Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

Lũy thừa modulo

Tính lũy thừa của một số rồi lấy dư theo modulo, bằng thuật toán lũy thừa nhanh.

Bạn sẽ học được gì

  • Nâng một số lên lũy thừa rất lớn trong O(log exponent) bước
  • Rút gọn mọi giá trị trung gian để tránh tràn số
  • Xử lý số mũ bằng 0 và modulus bằng 1

Đề bài

Xem bản gốc (English)

Hãy tính base^exponent mod modulus. Số mũ có thể lớn tới 10^18, nên không thể nhân với base ngần ấy lần; thay vào đó hãy dùng lũy thừa nhanh (bình phương và nhân): xét các chữ số nhị phân của số mũ, mỗi bước bình phương cơ số, và nhân nó vào kết quả khi chữ số đó là 1. Với mọi số mũ trong bài, cách này chỉ mất khoảng 60 bước.

Hãy viết modular_exponentiation(base, exponent, modulus).

Hãy lấy base modulo modulus ngay từ đầu và sau mỗi phép nhân. Vì modulus ≤ 10^9, tích của hai giá trị đã rút gọn nhỏ hơn 10^18 và vừa trong kiểu số nguyên có dấu 64 bit.

Đầu vào

base: Cơ số.

exponent: Số mũ.

modulus: Số dùng để lấy phần dư.

Đầu ra

Trả về base^exponent mod modulus, một giá trị từ 0 đến modulus − 1. Coi base^0 bằng 1 với mọi cơ số, kể cả 0, nên khi số mũ bằng 0 thì đáp án là 1 mod modulus.

Ràng buộc

0 ≤ base ≤ 10^18

0 ≤ exponent ≤ 10^18

1 ≤ modulus ≤ 10^9

Ví dụ

Ví dụ 1
Đầu vào:
base = 3
exponent = 13
modulus = 50

Kết quả mong đợi:
expected = 23
Đầu vào:
long long base = 3;
long long exponent = 13;
long long modulus = 50;

Kết quả mong đợi:
long long expected = 23;
Đầu vào:
long base = 3;
long exponent = 13;
long modulus = 50;

Kết quả mong đợi:
long expected = 23;

Giải thích

3^13 = 1,594,323, và 1,594,323 = 50 × 31,886 + 23, nên kết quả là 23.

Ví dụ 2
Đầu vào:
base = 2
exponent = 10
modulus = 1000

Kết quả mong đợi:
expected = 24
Đầu vào:
long long base = 2;
long long exponent = 10;
long long modulus = 1000;

Kết quả mong đợi:
long long expected = 24;
Đầu vào:
long base = 2;
long exponent = 10;
long modulus = 1000;

Kết quả mong đợi:
long expected = 24;

Giải thích

2^10 = 1024, và 1024 mod 1000 = 24.

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Xét từng chữ số nhị phân của số mũ, bắt đầu từ bit thấp nhất.

Gợi ý 2

Mỗi bước bình phương cơ số, và nhân nó vào kết quả khi bit hiện tại là 1.

Gợi ý 3

Khởi tạo kết quả bằng 1 % modulus, để khi modulus bằng 1 thì kết quả là 0.

Độ phức tạp mong đợi

thời gian O(log exponent), bộ nhớ phụ O(1)

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.