快速幂

zhangyimo · 2019-06-21 09:52:46 · 个人记录

再写题目时我们常常会遇到要求a的b次方的情况.这种情况下通常一个pow函数搞定

但是,超时!!!

这就需要一个十分有用的工具了

快速幂,顾名思义,十分快速的解决幂运算,先来看代码

int quickpow(int a, int b,int mod)
{
    int base=1;
    a%=mod;
    while(b>0)
    {
        if(b%2==1)
            base=(base*a)%mod;
        b=b/2;
        a=(a*a)%mod;
    }
    return base;
}

其实很好理解,就是把a^b换成a^b/2*a^b/2,这样就只用算a^b/2再来一个乘法就行了

非常简单有没有?

循环往复,最终b会变成1

这就是一道模版题一个快速幂搞定

代码如下

#include<iostream>
#include<iostream>
using namespace std;
long long a,b,m;
long long quickpow(long long a, long long b,long long mod)
{
    int base=1;
    a%=mod;
    while(b>0)
    {
        if(b%2==1)
            base=(base*a)%mod;
        b=b/2;
        a=(a*a)%mod;
    }
    return base;
}
int main( )
{
    cin>>a>>b>>m;
    cout<<quickpow(a,b,m);
    return 0;
}