Lũy thừa nhị phân - Binary Exponentiation Như bạn đã biết, để tính lũy thừa bậc $n$ của $x$ thì tồn tại 1 cách có độ phức tạp $O(n)$ để giúp chúng ta làm điều đó. Bài viết này sẽ hướng dẫn các bạn tìm lũy thừa của 1 số trong $O(logN)$. Lí thuyết: Để tìm $x^n$, ta có công thức như sau:\[\left\{\begin{matrix}1 \;\,\qquad \qquad khi \quad n = 0 \\x^{n - 1} \times x \quad khi \quad n > 1\end{matrix}\right.\] Cách làm này mất $n$ bước để thực hiện. Xét tính chất sau của lũy thừa:\[x^{a + b} = x^{a} \times x^{b}\] Ta có thể phân tích $x^n$ thành như sau:\[x^{n} = x^{\frac{n}{2}} \times x^{\frac{n}{2}} \quad khi \quad n \, mod \, 2 \, = \, 0\] \[x^{n} = x^{\frac{n}{2}} \times x^{\frac{n}{2}} \times x \quad khi \quad n \, mod \, 2 \, = \, 1\] Với tính chất này, ta có thể tính $x^n$ với $x^{\frac{n}{2}}$ mà không cần phải tìm $x^{\frac{n}{2} + 1}$, $x^{\frac{n}{2} + 2}$, ... làm gì nữa. Lặp đi lặp lại hành động này, ta sẽ tính được $x^n$ với độ phức tạp là $O(logn)$. Implementation:

int binary_exponentiation(int x, int n)
{
	if (n == 0) return 1;
	int k = binary_exponentiation(x, n / 2);
	k *= k;
	if (n % 2 == 1) k *= x;
	return k;
}

Một cách khác không dùng đệ quy:

int binary_exponentiation(int x, int n)
{
    int res = 1;
    while (n > 0) 
	{
        if (n % 2 == 1)
            res = res * x;
        x = x * x;
        n *= 2;
    }
    return res;
}