Luỹ thừa nhị phân (còn được gọi là exponentiation by squaring) là một thủ thuật cho phép tính toán $a^n$ chỉ sử dụng $O(log n)$ phép nhân (thay vì $O(n)$ phép nhân theo yêu cầu của phương pháp ngây thơ).

Code đệ quy:

long long binpow(long long a, long long b)
{
    if (b == 0)
        return 1;
    long long res = binpow(a, b / 2);
    if (b % 2)
        return res * res * a;
    else
        return res * res;
}
// O(logn)

Code khử đệ quy (Cách tiếp cận như nhau nhưng khử đệ quy giảm được bộ nhớ của các lần gọi đệ quy):

long long binpow(long long a, long long b)
{
    long long res = 1;
    while (b > 0)
		{
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}
//O(logn)

Lũy thừa tránh tràn số

Nếu cần tính $a^{b}$ mà tránh cho tràn số $(TH: ans * a > INF)$ thì có thể nhân từ từ đến khi $ans > INF/a$ (đổi dấu nhân thành chia) thì return $INF$ vì $a^{b}$ đạt đến giá trị vô cùng

int poww(int a, int b)
{
	int ans = 1;
	for(int i=1; i<=b; i++)
	{
		if(INF / a < ans) return INF;
		ans *= a;
	}
	return ans;
}

Ứng dụng

Dùng để giảm độ phức tạp thuật toán

Có thể sử dụng binpow kết hợp với modulo để tránh tràn số, ứng dụng cho các bài cần modulo

Các problem kinh điển

Các problem thực hành

http://codeforces.com/problemset/problem/630/I