Đề bài
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ụ
Đầ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.
Đầ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.