ACM | 演算法 | 快速冪

快速冪

​ 冪運算：\(x ^ n\)

​ 根據其一般定義我們可以簡單實現其非負整數情況下的函數

定義法：

int Pow (int x, int n) {
    int result = 1;
    
    while(n--) {
        result *= x;
    }
    
    return result;
}

​ 不難看出此時演算法的時間複雜度是\(O(n)\)，一旦n取較大數值，計算時間就會大大增加，極其容易出現超時的情況。

快速冪：

​ 首先要在此列舉兩個前提：

1. 電腦是通過二進位進行存儲數據的，對二進位數據可以直接進行操作。

2. \(2^n+2^n=2*2^n=2^{n + 1}\)

​ 對於\(x ^ n\)，其中n可以表示為m位的二進位形式，即\(n=n_12^0+n_22^1+n_32^3+\cdots+n_m2^{m-1}\)

​ 那麼\(x ^ n=x ^ {n_12^0+n_22^1+n_32^3+\cdots+n_m2^{m-1}}\)

​ 即\(x^n=x ^ {n_12^0}x^{n_22^1}x^{n_32^3}\cdots x^{n_m2^{m-1}}\)

​ 根據前提1，電腦可以直接對二進位格式存儲的數據進行讀取，那麼我們就可以對\(n\)一個個讀取再對其進行累乘。

​ 當取到第\(a\)位時，其乘數有通項公式：\(x^{n_a2^{a-1}}\)

​ 通過標準庫math，用代碼實現：

int Pow (int x, int n) {

    int result = 1;

    int a = 1;
    
    while(n) {
        if(n & 1) result *= round( pow(x, 1 << (a - 1)) );//round的作用在於double轉int時防止丟失精度，對1進行位運算是一種計算2的n次冪的快速方法
        n >>= 1;
        
        a++;
    }
    
    return result;
}

​ 但實際上這個調用了標準庫的代碼並沒有實現快速冪，因為仍然是採用pow()進行的運算

此處由 \(2^n+2^n=2\times2^n=2^{n + 1}\)

即\((x ^ {2 ^ {n}} )^2=x ^ {2\times 2 ^ {n}} =x ^ {2 ^ {n + 1}}\)

因此我們可以通過對前項進行二次冪運算得到後項

先得到首項\(f(1)=x^{2^{1-1}}=x\)

即令int f = x

具體實現：

int Pow (int x, int n) {

    int result = 1;

    int f = x;
    
    while(n) {
        if(n & 1) result *= f;

        f *= f;
        
        n >>= 1;
    }
    
    return result;
}

不難發現此時演算法的時間複雜度由其次數的二進位位數而決定，即\(O(m)\)也就是\(O([log_2n+1]-1)\)

另外因為此演算法常常用於計算大數，所以int類型最好都換成long long類型，防止溢出。

快速冪取模

​ 對\(x^n\)取模運算：\(x^n％p\)，當n極大時，同樣其運算量也會增大

​ 這就需要我們尋求一種快速解決的方法，此時可以運用我們上文所提到的快速冪演算法

​ 引論：\((m*n)％p=((m％p)(n％p))％p\)

​ 證明如下：令\(\left\{ \begin{array}{c} m=(ip+c)& (i\in\mathbb{Z} )\\ n=(jp+d) & (j\in\mathbb{Z} )\end{array} \right.\)

​ 則有\(\left\{ \begin{array}{c} m％p=c\\ n％p=d \end{array} \right.\)

​ 原式\((m*n)％p\\=((ip+c)(jp+d))％p\\=(jip^2+jpc+ipd+cd)％p\\=(jip^2+jpc+ipd+cd)％p\\=((jip+jc+id)p+cd)％p\)

​ 引論2：\((np+a)％p=a％p\quad (n\in\mathbb{Z} )\)

​ 證明如下：設\(f(n,p,a)=(np+a)％p\quad (n\in\mathbb{Z} )\)

​ 則由定義有\((np+a)％p=\frac{np+d}{p}-\{[\frac{np+d}{p}+1]-1\}\\ =d-p\{[\frac{d}{p}+1]-1\}\)

​ 顯而易見，\((np+a)％p=a\)與\(n\)無關

​ 令\(n=0\)得\((np+a)％p=a％p\quad (n\in\mathbb{Z} )\\ Q.E.D\)

​ \(=(cd)％p\\=((m％p)(n％p))％p\)

​ 即\((m*n)％p=((m％p)(n％p))％p\\ Q.E.D\)

​ 因此對於\(x^n％p\)

​ 可以寫成\((x ^ {n_12^0}x^{n_22^1}x^{n_32^3}\cdots x^{n_m2^{m-1}})％p\\ =((x ^ {n_12^0}％p)(x^{n_22^1}％p)(x^{n_32^3}％p)\cdots (x^{n_m2^{m-1}}％p))％p\)

​ 並且由之前的推定\((x ^ {2 ^ {n}} )^2=x ^ {2\times 2 ^ {n}} =x ^ {2 ^ {n + 1}}\)

​ 有\((x ^ {2 ^ {n}} ％p)^2％p =(x ^ {2 ^ {n}})^2％p=x ^ {2 ^ {n + 1}}％p\)

​ 代碼實現：

int Mod (int x, int n, int p) {

    int result = 1;

    int f = x % p;
    
    while(n) {
        if(n & 1) result = (result * f)%p;

        f = (f * f)%p;
        
        n >>= 1;
    }
    
    return result;
}