快速幂取模算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了快速幂取模算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1912字，纯文字阅读大概需要3分钟。

内容图文

问题引入

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

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

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;
}

内容总结

以上是互联网集市为您收集整理的快速幂取模算法全部内容，希望文章能够帮你解决快速幂取模算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---