更多分治例題

快速冪

快速冪算法是一種高效計算大整數指數冪的方法。傳統的方法是通過連續乘法來計算 a 的 b 次方，但當 b 非常大時，這種方法的效率非常低。快速冪算法通過分治的策略來減少所需的乘法操作，從而大大提高了效率。

通過將指數 b 分解成二進制表示，我們可以將 a 的 b 次方分解成較小的部分，每個部分都是 a 的某個 2 的冪。這樣，我們只需要計算 log(b) 個乘法，而不是 b 個乘法。

int fastPow(int a, int b) {
	if (b == 0) return 1;
	return fastPow(a, b / 2) * fastPow(a, b / 2) * (b & 1 ? a : 1);
}

或是也可以疊代的方式實作：

int fastPow(int a, int b) {
    int res = 1;
    while (b > 0) {
        if (b & 1) res *= a;
        a *= a;
        b >>= 1;
    }
    return res;
}