【筆記】Exponentiating by Squaring 快速冪

  • 【用途】倍增法:利用「指數」的二進位表示法,來決定計算哪些冪次。
  • 【實作】函式 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)
  • 【時間複雜度】
    • 樸素做法:O(n)
    • 快速冪:O(log(n))
  • 【練習】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;
}
分享本文 Share with friends