当前位置：首页 > article >正文

算法14、基础二分查找的运用（快速幂）

article 2025/1/8 4:54:27

🌰1、快速幂1--求a的b次方

晴问算法

当指数很大，超过或接近10的9次方，就应该使用二分快速幂：

快速幂的二分算法，设b为指数

当b是奇数，a的b次方 == a * a的(b-1)次方；

当b是偶数，a的b次方 == a的b/2次方 * a的b/2次方；

接下来分别运用递归分治和递推分治的思想写代码，详细理解可见《算法笔记》

知识点：位与运算&

奇数的二进制末位一定是1，偶数的二进制末位一定是0；

与运算：只有当双方都是1时结果才是1.其它情况都是0；

位运算会把比较的两个数的二进制位对齐，如果位数不同，会在更短的二进制数的高位补0。

当要判断奇偶数的数是Long long类型时，%2的效率会很慢，而位与运算的时间复杂度是o(1)相当高效，所以我们就可以使用if（x & 1）判断，若结果是1（任何非零值是true)说明b的末位是1，即说明x是奇数，否则是偶数。

注意，要用long long型存储数据。

做法1-递归写法

#include <iostream>
using namespace std;
typedef long long LL; 
long long binaryPow(LL a, LL b){
    if(b == 0)//递归边界
        return 1;
    if(b & 1)//若指数是奇数
        return a * binaryPow(a, b-1);
    else{//若指数是偶数
        LL temp = binaryPow(a, b/2);
        return  temp * temp;
    }
}
int main(){
    LL a, b;
    cin >> a >> b;
    printf("%lld\n", binaryPow(a, b));
}

做法2-迭代写法

我们可以把指数b写成若干二次幂之和：

比如b == 13时，先把13改成二进制，13 = 8 + 4+ 0*2 + 1, 就是1101, 3号位、2号位、0号位为1。

那么a的b次方，就可以写成：

a的13次方 == a的8次方 * a的4次方 * （0*a的2次方） * a的1次方

显然，a的b次方就可以写成是若干a^(2的i次方) 之积，如果b的二进制的i号位为1，那么该a^(2的i次方)就被选中，应该乘上该项。

在迭代过程中，可用位与运算判断b的末位是否为1，若为1就乘上该项；判断完该位要往前一位判断的时候，可/2，也可将b的二进制右移一位即b >>= 1，结果是相同的；

同时可以注意到，1次方->2次方->4次方->8次方，从第一项a开始，每一项都是前一项的平方，因此可以通过a = a*a 来更新每一项；

#include <iostream>
using namespace std;
typedef long long LL; 
int main(){
    LL a, b;
    cin >> a >> b;
    LL ans = 1;
    while( b > 0){
        if(b & 1){//若b的末位为1， 那么应该乘上该项
            ans  *= a;
        }
        a = a*a;//更新每一项；
        b >>= 1;//更新右移b；
    }
    printf("%lld\n", ans);
}

🌰2、快速幂2-求a的b次方取模

晴问算法

再上一题基础上，再运用(a1 * a2 ) % m == (a1%m * a2%m ) %m;

这意味着我们可以在每一步计算时取模，从而避免中间结果过大。对于一般情况的 (a1 * a2 * a3 .....) % m，可以写成以下迭代形式：

迭代公式：

result = 1

对于每个 ai：

result = result * (ai % m) % m

也就是说，我们只需要保证对中间结果result取模，以及对下一个乘项取模。

做法1-递归写法

#include <iostream>
using namespace std;
typedef long long LL; 
long long binaryPow(LL a, LL b, LL m){
    if(b == 0)//递归边界
        return 1;
    if(b & 1)//若指数是奇数
        return ( (a %m) * (binaryPow(a, b-1, m) % m) ) %m;
    else{//若指数是偶数
        LL temp = binaryPow(a, b/2, m) % m;
        return  (temp * temp) % m;
    }
}
int main(){
    LL a, b, m;
    cin >> a >> b >> m;
    if(m == 1)//若模数为1，那么结果都为0，因为任何正整数对1取模都为0
        printf("0\n");
    printf("%lld\n", binaryPow(a, b, m));
}

做法2-迭代写法

#include <iostream>
using namespace std;
typedef long long LL; 
LL fastPow(LL a, LL b, LL m){
    LL ans = 1;
    while( b > 0){
        if(b & 1){
            ans = ans * a % m;//* 、%的优先级相等
        }
        a = a * a % m;
        b >>= 1;
    }
    return ans;
}
int main() {
    LL a, b, m;
    scanf("%lld%lld%lld", &a, &b, &m);
    printf("%lld", fastPow(a, b, m));
    return 0;
}

查看全文

http://www.kler.cn/a/469649.html