快速幂取模算法

佚名 5年前 (2019-08-06) 算法 2054人围观抢沙发百度已收录

问题引入

快速幂用于求解 \(a ^ n\ mod\ m\) 的结果。

朴素的做法是直接用循环求解，时间复杂度 \(O(n)\)。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

typedef long long ll;
ll power(ll a, ll n, ll m) {
    ll result = 1;
    for (int i = 0; i < n; ++i) {
        result = (result * a) % m;
    }
    return result;
}

缺点很明显，一是效率低，容易超时，二是指数爆炸，容易爆 \(long\ long\)。

快速幂分治思想

可以将问题分解成如下的子问题：

\[ a^n\ mod\ m = \begin{cases} 1\ mod\ m, & n = 0\\ (a^{n/2} \cdot a^{n/2}) \ mod\ m, & n是偶数\\ (a \cdot a^{n/2} \cdot a^{n/2})\ mod\ m, & n是奇数 \\ \end{cases} \]

写成递归的形式

\[ power(a, n, m) = \begin{cases} 1\% m, & n = 0\\ power(a^2, n/2, m) \% m, & n是偶数\\ (a * power(a^2, n/2, m)) \% m, & n是奇数 \\ \end{cases} \]

代码如下

typedef long long ll;
ll quick_mod(ll a, ll n, ll m) {
    if (n == 0)
        return 1;
    else if (n % 2 == 0) 
        return quick_mod(a * a, n / 2, m) % m;
    else 
        return ((a % m) * quick_mod(a * a, n / 2, m)) % m;
}

上述代码就是快速幂了。

朴素方法计算 \(a ^ n\) 其实计算了两遍 \(a ^ {n / 2}\) 再相乘，其实计算一次 \(a ^ {n / 2}\) 就够了，因为 \(a ^ {n / 2}\) 的平方就是 \(a ^ n\)。而计算 \(a ^ {n / 2}\) 又等价于计算 \(a ^ {n / 4}\) 的平方...，因此只需 \(log(n)\) 次就可以计算出结果。采用分而治之的方法将时间复杂度降为 \(O(log(n))\)。

由于递归比较慢，且容易爆栈，因此改成非递归的形式。

typedef long long ll;
ll quick_mod(ll a, ll n, ll m) {
    if(n == 0)
        return 1 % m;

    ll res = 1;
    while (n > 0) {
        if (n % 2 == 0) { 
            a = (a * a) % m;
            n = n / 2;
        } else {
            res = (res * a) % m;
            a = (a * a) % m; 
            n = n / 2;
        }
    }
    return res;
}

可以发现上述代码有重复部分，还可以简化。

typedef long long ll;
ll quick_mod(ll a, ll n, ll m) {
    if(n == 0)
        return 1 % m;

    ll res = 1;
    while (n > 0) {
        if(n % 2) { 
            res = (res * a) % m;
        }
        a = (a * a) % m; 
        n = n / 2;
    }
    return res;
}

进一步优化

typedef long long ll;
ll quick_mod(ll a, ll n, ll m) {
    if(!n)
        return 1 % m;

    ll res = 1;
    while (n) {
        if(n & 1) {  // 二进制最后一位为 1是奇数
            res = (res * a) % m;
        }
        a = (a * a) % m; 
        n >>= 1;  // 右移一位就是整除 2
    }
    return res;
}