Lũy Thừa Nhị Phân

1. Lũy Thừa Nhị Phân Sử Dụng Đệ Quy

Lũy thừa nhị phân - Binary exponentiation là một thuật toán giúp bạn tính aⁿ với độ phức tạp là O(logN) thay vì duyệt vòng lặp từ 1 tới n.

Dựa theo công thức sau (ảnh : CP-Algorithm) :

image

Ở đây bài toán con nhỏ nhất khi n = 0 thì thì ta có aⁿ = 1

Ngược lại bạn có thể tính an thông qua a^n/2 , nếu n chẵn thì an = a^n/2 * a^n/2 ví dụ 2¹⁰ = 2⁵ * 2⁵. Nếu n lẻ thì aⁿ = a^n/2 * a^n/2 * a ví dụ 2¹⁰ = 2⁵ * 2⁵*2¹

Mã nguồn :

#include "iostream"

using namespace std;

#define ll long long

ll binpow(int a, int n){
	if(n == 0){
		return 1;
	}
	ll X = binpow(a, n / 2); // a^(n/2)
	if(n % 2 == 1){
		return X * X * a;
	}
	else{
		return X * X;
	}
}

int main(){
	cout << binpow(2, 10) << endl;
	cout << binpow(2, 50) << endl;
	return 0;
}

2. Lũy Thừa Nhị Phân Sử Dụng Vòng Lặp

Phương pháp tính sử dụng vòng lặp dựa trên biểu diễn nhị phân của số mũ, ví dụ bạn cần tính 5²⁹ ta có thể viết dưới dạng 5^11101₂= 5¹⁶* 5⁸ * 5⁴ * 5¹

Ở đây mình sẽ lấy ví dụ số mũ là 29, bạn thấy để cần tính 5²⁹thì bạn cần có 5¹⁶, 5⁸, 5⁴, 5¹ tương ứng với các bit 1 ở vị trí 4, 3, 2, 0 của số 29 dạng nhị phân

Vì thế để tính được 5²⁹ bạn chỉ cần xét từng bit của số 29 từ cuối về, nếu bit thứ K là bit 1 thì bạn sẽ tính nhân 5^X vào kết quả với X = 2^K

image

Bây giờ bạn chỉ cần biết cách xét từng bit ở dạng nhị phân của số mũ n là sẽ có thể bắt đầu code được. Đầu tiên bạn cần để ý rằng tất cả những số lẻ sẽ đều có bit cuối cùng là bit 1, ví dụ N = 29 = 11101₂, N = 19 = 10011₂.

Vậy khi bạn đang xét N thì bạn chỉ cần kiểm tra N là số lẻ thì bạn có thể biết bit cuối cùng của nó là số 1. Sau khi xét xong bit hiện tại thì bạn sẽ phải dịch sang phải để xét bit tiếp theo, bước này được thực hiện bằng phép dịch bit phải (tương đương phép chia cho 2)

Ví dụ về việc xét từng bit của 1 số dựa vào phép dịch bit sang phải :

image

Mã nguồn :

#include "iostream"

using namespace std;

#define ll long long

ll binpow(ll a, ll n){
	ll res = 1;
	while(n != 0){
		//Neu bit cuoi cung cua n la bit 1 
		if(n % 2 == 1){
			res *= a;
		}
		//Dich bit 
		n /= 2;
		//Nhan a voi a
		a = a * a;
	}
	return res;
}

int main(){
	cout << binpow(2, 10) << endl;
	cout << binpow(2, 50) << endl;
	return 0;
}

Ví dụ : a = 5, n = 29

Vòng lặp 1 : n = 29 = 11101, bit cuối là 1 nên res *= a = 5, n / 2 = 14, a = a * a = 5²
Vòng lặp 2 : n = 14 = 1110, bit cuối là 0 nên không cần nhân 5² vào kết quả, res = 5, n = n / 2 = 7, a = a * a = 5⁴
Vòng lặp 3 : n = 7 = 111, bit cuối là 1 nên res *= a = 5⁵, n = n / 2 = 3, a = a * a = 5⁸
Vòng lặp 4 : n = 3 = 11, bit cuối là 1 nên res *= a = 5¹³, n = n / 2 = 1, a = a * a = 5¹⁶
Vòng lặp 5 : n = 1 = 1, bit cuối là 1 nên res *= a = 5²⁹, n = n / 2 = 0, a = a * a = 5³²
Dừng vòng lặp khi n = 0

Bạn cũng có thể cài đặt bằng cách sử dụng toán tử bit như sau :

#include "iostream"

using namespace std;

#define ll long long

ll binpow(ll a, ll n){
	ll res = 1;
	while(n != 0){
		//Neu bit cuoi cung cua n la bit 1 
		if(n & 1){
			res *= a;
		}
		//Dich phai 1 bit 
		n >>= 1;
		//Nhan a voi a
		a *= a;
	}
	return res;
}

int main(){
	cout << binpow(2, 10) << endl;
	cout << binpow(2, 50) << endl;
	return 0;
}

Mỗi vòng lặp n sẽ bị giảm 2 lần nên số vòng lặp cần phải thực hiện tương ứng với số bit của n ở dạng nhị phân là ⌈log₂n⌉. Độ phức tạp của thuật toán là O(log₂N), cực kỳ nhanh

3. Lũy Thừa Chia Dư

Vì độ phức tạp của thuật toán lũy thừa nhị phân chỉ là O(log₂N) nên bạn có thể tính lũy thừa với số mũ rất lớn, ví dụ 10¹⁸. Vì kết quả của lũy thừa quá lớn nên thường được chia dư cho một số cho trước, mục này mình sẽ hướng dẫn cách bạn tính a^b%c.

Bạn cần chút kiến thức cơ bản về đồng dư là có thể giải quyết được bài toán này, nếu chưa biết về đồng dư bạn có thể tham khảo tại đây

Link submit : https://cses.fi/problemset/task/1095

Mã nguồn :

#include "iostream"

using namespace std;

#define ll long long

ll binpow(ll a, ll n, ll c){
	ll res = 1;
	a %= c;
	while(n != 0){
		//Neu bit cuoi cung cua n la bit 1 
		if(n % 2 == 1){
			res *= (a % c);
			res %= c;
		}
		//Dich phai 1 bit 
		n /= 2;
		//Nhan a voi a
		a *= (a % c);
		a %= c;
	}
	return res;
}

int main(){
	cout << binpow(2, 1000000000000000, 10) << endl;
	cout << binpow(11928128125, 5000000000, 10) << endl;
	return 0;
}

Video Tutorial :

29tdEwMlCd4