快速幂||取余运算(模板)...

2019-04-29 08:49:02来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

第二个板子!!!(第一个板子还没发)

有那么一种算法可以让计算a^b变得更快,那就是快速幂。如果直接暴力计算的话需要计算b次。时间蛮长的。

题目描述:

  输入a,b.(a,b为整数)计算a^b。

输入输出格式

输入格式:

三个整数a、b。.

输出格式:

输出“a^b=s”

s为运算结果

 

前提:你需要了解二进制,十进制。位运算的知识(当然也可以没有,万事皆可模拟。)

代码:

//省略...... 
long long quickpow(int a,int b)
{
    long long ans=1,base=a;
    while(b!=0)
    {
        if(b&1!=0) ans*=base;    
        base*=base;
        b>>=1;    //将b的二进制数向右移一位(相当于将b的二进制数的最后一位抹掉。)
    }
    return ans;
}

但由于是乘方运算所以即便是long long也容易爆!

input:

2 11

output:

2048

先讲一下(&、>>)位运算.

&:‘&’叫做按位与。作用:把参与运算的两个数对应的二进制相与,只有对应的二进制均为1时,结果的对应位才为1,否则为0。(11)10==(1011)2.

>>:

我们以此输入输出来讲解一下。

a为底数,b为指数。


原文链接:https://www.cnblogs.com/poi-bolg-poi/p/10784919.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:C++ : 内联函数和引用变量

下一篇:shell---命令解析器---简单操作快捷键