快速幂算法(2022.7.19更新)


快速幂

快速幂以下简称(fpow)是math.h或cmath里的内置函数pow的升级版(只不过是比pow快了一些)

2022.7.19 SD夏令营具体学了学快速幂,这次修改主要是改了改思想和具体操作,原理不变

原理:

通过将指数拆分成几个因数相乘的形式,来简化幂运算。

具体操作:

将指数转化为二进制,如果这一位上是1,那就乘上这一位上的信息(即x的几次方,按照二进制的规则来即可)

二进制位数   ……4  3  2  1

对应的十进制  ……x^3 x^2 x^1 x^0

模拟一下以便于理解

e.g. 我们算3的10次方,10的二进制为1010,首先,最后一位为0,x*=x,因为二进制的每向左移一位,就更新为原来的二次方,右移。

现在,最后一位为1,那么答案乘上x,更新x,右移。

最后一位为0,x*=x,右移。

最后一位为1,ans*=x,x*=x,右移,没有位数了,退出。

代码:

//long long fastpower(long long,long long,long long);//觉得函数主体碍眼就打函数声明
long long fastpower(long long x,long long y,long long mod)
{
    long long ans=1;
    while(y)
    {
        if(y&1)//位运算 等价于y%2==1 这里判断指数的二进制位数上是否为1,以此来决定要不要乘
        {
            (ans*=x)%=mod;//记得取模,看题目要求
        }
        y>>=1;//位运算 将最后一位移除; 
        x*=x;//更新位数上的信息,即x的几次幂
    }
    return ans%mod;
}

位运算可以提高速度(可能快不了多少,但很高大上)

 

原创文章,作者:carmelaweatherly,如若转载,请注明出处:https://blog.ytso.com/275478.html

(0)
上一篇 2022年7月19日
下一篇 2022年7月19日

相关推荐

发表回复

登录后才能评论