快速冪

快速冪是一個處理整數冪次的演算法,可以在

O(log n) 的複雜度完成任務
一般來說我們處理冪次問題
a n
會使用以下方法:

int ans = 1;
for(int i = 0; i < n; i++)
    ans *= a;
cout << ans;

這種方法最直觀,但是卻需要

O(n) 的時間才能完成
對於數字過大的數字實在太耗時
因此我們會需要用到快速冪來處理這個問題

原理說明

要解釋快速冪的原理,需要用到一個性質

二進制

每個十進制非負整數

(n)10 都可以被拆解成二進制
(n)10=a0×20+a1×21+...+ak×2k
,其中
ai=0 or 1, iN

則可寫成二進制:
(akak1...a1a0)2

舉例來說:

(61)10=1×20+0×21+1×22+1×23+1×24+1×25=(111101)2

換種角度來看,也可以將一個數字看作有一數列

<2 n>
二進位就是看這數列中要取哪幾項相加才會是我要的數字
1
就是取該項,
0
就是不取該項

快速冪原理

原理說明

設今天有一個數字

b n,可以先把
n
變成二進制的寫法
得到
b n=b (a0×20+a1×21+...+ak×2k)=b a0×20×b a1×21×...× b ak×2k
。其中,
ai{0,1} (0ik)

列舉序列

要窮舉序列

<b20,b21,b22,..., b2k> 是很簡單的,只需要先計算
k
值,再使用
for
迴圈就可以實現

#define ll long long
void enumerate_sequence(ll b, ll n){
    ll k = log2(n);
    for(int i = 0; i <= k; i++){
        b *= b;
    }
}

取 or 不取

再來就是要來判斷

ai
0
還是
1
。若
1
則將答案乘上去,
0
就不理他

#define ll long long
ll pick_sequence(ll b, ll n){
    ll k = log2(n), ret = 1;
    for(int i = 0; i <= k; i++){
        if(n & (1 << i)) // 是 1 就乘上去
            ret *= b;
        b *= b;
    }
    return ret; // 回傳答案
}

舉例

797=7 (1100001)2=720×726×727=71×732×7128

程式碼實作

可以用

while 迴圈來實現,這樣就不需要
k
值了

  • 每次迴圈都重複
    n
    >>=
    1
    ,這就相當於從左往右看
    n
    的位元
  • 判斷
    n
    的每給位元是否為
    1
    ,是的話就乘起來
  • 每次迴圈將
    b
    *=
    b
    ,這就相當於在算第
    i
    項時的
    b2i
#define ll long long
ll fpow(ll b, ll n){
    ll ret = 1;
    while(n){
        if(n & 1)
            ret *= b;
        b *= b;
        n >>= 1;
    }
    return ret;
}

備註

  • 快速冪的原理在倍增法 (binary lifting) 也有很大的用處
  • 矩陣乘法也可以快速冪
  • 競程題目數字最大
    1018
    ,若要求
    a1018
    ,使用快速冪可以把步迴圈數壓在
    60
    以內
    (幾乎就是常數了)

題目練習

Zerojudge d636. 大爆炸bomb
Zerojudge d219. 00374 - Big Mod
Zerojudge k137. 次方練習
CSES Exponentiation
CSES Exponentiation II


ShanC 程式競賽筆記
作者: ShanC
更新: 2024/9/13