Tác giả:
Reviewer:
Phép tính lũy thừa là một trong những phép tính cơ bản nhất, xuất hiện rất nhiều trong các công thức toán học và tất nhiên cũng có hàng tá các ứng dụng trong tin học. Vậy đâu là cách tính lũy thừa hiệu quả nhất trong lập trình và những ứng dụng của lũy thừa là gì, mời bạn đọc cùng tìm hiểu.
Để gợi ý cho bạn đọc, hãy cùng giải câu đố sau: hãy tính bằng các phép nhân sao cho số phép nhân cần dùng là ít nhất. Trong mỗi phép nhân, bạn chỉ được sử dụng thừa số là hoặc là kết quả của một phép nhân trước đó.
Nếu tìm được số phép nhân ít nhất là thì xin chúc mừng bạn, đó là câu trả lời tối ưu. Cách thực hiện như sau:
Vậy chỉ cần phép nhân để tính , nhỏ hơn nhiều so với số phép nhân cần thực hiện nếu tính theo định nghĩa (tích của thừa số ).
Đây chính là ý tưởng cho thuật toán tính lũy thừa bằng phương pháp nhị phân.
Với mọi số tự nhiên , công thức tổng quát như sau:
Dựa vào công thức trên, ta có hàm tính
long long Pow(long long a, long long b) {
if (!b) return 1;
long long x = Pow(a, b / 2);
if (b % 2 == 0)
return x * x;
else
return x * x * a;
}
Dưới đây là một cách cài đặt khác không cần đệ quy. Trong cách này ta phân tích
Phân tích
Cài đặt:
long long Pow(long long a, long long b) {
long long ans = 1;
while (b > 0){
if (b % 2) ans = ans * a;
a = a * a;
b /= 2;
}
return ans;
}
Thuật toán có độ phức tạp là
Khi
Biết rằng phép nhân không làm ảnh hưởng đến phép chia lấy dư, vì vậy chỉ cần thêm các thao tác chia lấy dư mỗi khi thực hiện phép nhân, ta được hàm Pow(a, b, M)
như sau:
long long Pow(long long a, long long b, long long M) {
long long ans = 1;
while (b > 0){
if (b % 2) ans = ans * a % M;
a = a * a % M;
b /= 2;
}
return ans;
}
Với các giá trị
Một tính chất khác trong phép lũy thừa:
Trong các trường hợp
Để hiểu hơn về các tính chất, các bạn có thể tham khảo định lý Fermat nhỏ và hàm phi Euler.
Một ví dụ điển hình ứng dụng tính chất bên trên là tính
Cần tính
Thoạt nhìn, đây là một vấn đề rất đơn giản, ta có thể lấy
Tuy nhiên trong một số trường hợp giá trị
Vì vậy ta cần "nhân nhị phân" (một số tài liệu gọi là "nhân Ấn Độ"), với ý tưởng tương tự như lũy thừa nhị phân. Công thức như sau:
Cài đặt:
long long Mul(long long a, long long b) {
if (!b) return 0;
long long x = Mul(a, b / 2);
if (b % 2 == 0)
return 2 * x % m;
else
return (2 * x + a) % m;
}
Để hiểu rõ phần này, bạn đọc cần nắm các kiến thức cơ bản về nhân ma trận
Ứng dụng lũy thừa nhị phân kết hợp với nhân ma trận là một ứng dụng phổ biến, điển hình là bài toán tính số Fibonacci thứ
Dãy số Fibonacci được định nghĩa như sau:
Bài toán đặt ra là tìm
Một trong những cách thực hiện điều này là áp dụng kiến thức "nhân ma trận".
Từ ma trận
Vì phép nhân ma trận có tính chất kết hợp nên ta dễ dàng áp dụng kĩ thuật lũy thừa nhị phân (thay số nguyên thành ma trận) để đạt được độ phức tạp
Bài viết được tham khảo từ Algorithms for Competitive Programming.