Nguồn: HackerEarth và 1 số bài viết trên Wikipedia
Người dịch: Bùi Việt Dũng
Xét bài toán tính , với là dấu đồng dư thức và có thể rất lớn (ví dụ ).
có thể viết là với chữ . Do đó ta có thể nhân lần để có được kết quả.
long long power(long long a, long long b, long long c) {
long long ans = 1;
for(int i = 1; i <= b; i++) {
ans *= a;
ans %= c;
}
return ans;
}
Trong mỗi lần lặp, biến chứa kết quả được nhân với . Ngoài ra, ta cần đảm bảo sẽ không vượt quá trong các lần lặp, vì thế ta lấy phần dư khi chia cho (ans = ans % c
). Ta làm được vậy là nhờ tính chất .
Vì vậy trong code trên ta tính bằng cách tính .
Độ phức tạp của thuật toán: .
Dễ dàng nhận thấy thuật toán trên không hiệu quả, vì thế ta cần tìm thuật toán hiệu quả hơn. Ta có thể giải bài toán này với độ phức tạp bằng kĩ thuật lũy thừa bằng cách bình phương (exponentiation by squaring). Kĩ thuật này chỉ cần lần bình phương và phép nhân để ra kết quả. Rõ ràng cách giải này hiệu quả hơn nhiều lần so với thuật toán "ngây thơ".
Ta biết rằng có thể được viết dưới dạng:
nếu chia hết cho 2.
nếu không chia hết cho 2.
nếu .
int sqr(int x) {
return x*x;
}
int pow(int a, int b, int MOD) {
if (b == 0) return 1 % MOD;
else
if (b % 2 == 0)
return sqr(pow(a, b/2)) % MOD;
else
return a * (sqr(pow(a, b/2)) % MOD) % MOD;
}
Giả sử ta có , khi đó kết quả là
Do lẻ, nên hàm gọi hàm để tính
Trong hàm , do chẵn nên
Trong hàm , do lẻ nên .
Trong hàm , do nên ta trả về 1.
Quay lại hàm : hàm này trả về giá trị 2.
Quay lại hàm : hàm này trả về giá trị 4.
Quay lại hàm : hàm này trả về giá trị .
Vậy ta có .
Độ phức tạp của thuật toán: