【算法学习笔记】33：快速幂的递归及循环实现

快速幂原理

要计算$a^b$，$a^{b}modp$，可以考虑用折半的方式缩小计算量。

例如要计算$2^{13}$，只要计算$2^6$乘以自己，再乘以一个多出来的2。

而要计算$2^6$，只要计算$2^3$乘以自己。

而要计算$2^3$，只要计算$2^1$乘以自己，再乘以一个多出来的2。

也就是每次把$b$折半下取整，当$b$是偶数时：
$$a^b=a^{\frac{b}{2}}\cdot a^{\frac{b}{2}}$$
当$b$是奇数时只要多乘以一个$a$：
$$a^b=a^{\frac{b}{2}}\cdot a^{\frac{b}{2}}\cdot a$$

如果需要对$p$取模，只要在每一步乘法之后取模就可以了。

例题：AcWing 875. 快速幂

递归实现

从前面的原理很容易得到如下的递归实现。

#include <iostream>

using namespace std;

typedef unsigned long long ULL;

ULL qmi(ULL a, ULL b, ULL p) {
    if (b == 1) return a % p;
    
    ULL res = qmi(a, b >> 1, p);
    res = res * res % p;
    if (b & 1) res = res * a % p;
    
    return res;
}

int main() {
    int t; cin >> t;
    
    while (t -- ) {
        ULL a, b, p; cin >> a >> b >> p;
        cout << qmi(a, b, p) << endl;
    }
    
    return 0;
}

循环实现

从前面的原理理解循环实现不直观。可以考虑$b$的二进制表示。例如$b=0b1101$也就是$2^3+2^2+2^0=13$，所以：

$$a^{2^3+2^2+2^0}=a^{2^3}\cdot a^{2^2}\cdot a^{2^0}$$

这正是因为$b$的从低到高0、2、3二进制位置是1导致的。

又因为
$$(a^{2^i}{)}^2=a^{2^{i+1}}$$
因此只需要循环的从最低位（第0位）开始，每次通过把$a$和自己相乘计算一下$a^{2^i}$，只要$b$的相应二进制位置是1，就把这个数乘进res里即可。

#include <iostream>

using namespace std;

typedef unsigned long long ULL;

ULL qmi(ULL a, ULL b, ULL p) {
    ULL res = 1;
    
    while (b) {
        if (b & 1) res = res * a % p;
        b >>= 1;
        a = a * a % p;
    }
    
    return res;
}

int main() {
    int t; cin >> t;
    
    while (t -- ) {
        ULL a, b, p; cin >> a >> b >> p;
        cout << qmi(a, b, p) << endl;
    }
    
    return 0;
}

原文地址：https://blog.csdn.net/SHU15121856/article/details/145169364

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！