MENU

快速幂取模

April 4, 2020 • Read: 379 • 算法

快速幂取模的算法是寒假的时候就学了的,那我为什么又在这里写呢?其实原因很简单,第一次学的时候没有很好的理解,所以又写了一遍,好了,废话不多说,开始干吧

为何有快速幂?

C语言不是有%(取模)符号么,那我们要快速幂干嘛?顾名思义,快速幂,讲究的就是一个“快”字,朴素算法中,直接计算a^b%c(对a的b次方取c的模)会导致出现一个相当麻烦的地方,就是a^b会产生一个相当大的数字,数字可能会超过C语言提供的整数范围从而导致程序错误,因此,快速幂取模应运而生,他不但可以节省空间,还能有较快的速度

快速幂的原理是什么呢?

对于取模运算,有一个公式:

(a*b)%c=(a%c)*(b%c)%c

我们可以在这个式子上稍动一些手脚,比如:

(a2)%c=(a%c)(a%c)%c=(a%c)^2 %c

将大数拆成多个数,不但可以避免出现超过范围的数,也能够让幂取模的运算更有效率

那该怎么写呢?

1.非递归:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//将long long型用ll表示
ll quickmod(ll a,ll b,ll c)
{
    int ret=1;
    //这里如果a==c要进行单独判断,否则答案会等于1
    while(b) //当b不等于0时
    {
        if(b&1) //判断是否为奇数,相当于b%2
            //2&1=0,3&1=1
            ret=ret*a%c;
        a=a*a%c;
        b>>=2; //等同于b/=2
    }
    return ret;
}
 
int main(){
    ll a,b,c;
    cin>>a>>b>>c;
    if (b==0){
        int ret=a%c;
        printf("%lld^%lld mod %lld=%d",a,b,c,ret);
    }
    else {
        int ret=quickmod(a,b,c);
        printf("%lld^%lld mod %lld=%d",a,b,c,ret);
    }
    return 0;
}

2.递归:(这里我就简写了...)

typedef long long ll;
ll binaryPow(ll a, ll b, ll m){
    if(b == 0)
        return 1;
    else if(b % 2 == 1)
        return a * binaryPow(a, b - 1, m) % m;
    else{
        ll num = binaryPow(a, b/2, m) % m;//优化 
        return num * num % m;
                // 不直接写成return binaryPow(a, b/2, m) * binaryPow(a, b/2, m)
    }
}

相关例题:【洛谷P1226】https://www.luogu.com.cn/problem/P1226

Last Modified: April 22, 2020
Archives Tip
QR Code for this page
Tipping QR Code