- 【用途】倍增法：利用「指數」的二進位表示法，來決定計算哪些冪次。
- 【實作】函式 pow_mod(a, b) 計算 ab % MOD
- 比如 b = 5 (二進位表示為101)，這些bits按照從右(LSB)到左(MSB)的順序使用。
- 5 = 22 + 20
- a5 = a(2^2) * a(2^0)
- Line-13：不斷地乘上自己(squaring)
- 【時間複雜度】
- 【練習】Codeforces 1228C. Primes and Multiplication
ll pow_mod(ll a, ll b){
//快速冪 (a^b) % MOD
ll ret = 1;
ll now = a;
while (b) {
//b = 5 = b'101
//a^b = a^5 = a^4 * a^1
if (b & 1) {
//需要這個冪次
ret *= now;
ret %= MOD;
}
now *= now; //a -> a^2 -> a^4 -> ...
now %= MOD; //避免溢位
b >>= 1; //b 的二進位數字往右移一位元
}
return ret;
}
Post Views (since April 2021) : 512