模板||快速幂

2019-05-16 23:54:34来源:博客园 阅读 ()

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

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

题目描述:

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

输入输出格式

输入格式:

两个整数a、b。.

输出格式:

输出“a^b=s”

s为运算结果

 

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

没有位运算的:

复制代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<cmath>
using namespace std;
char e[10001];
int cd;
long long quickpow(long long a,char b[]) {
    long long ans=1,base=a;
    while(cd!=-1) {
        if(int(b[cd])!=0) ans*=base;//最后一位是1的话。
        base*=base;
        cd--;//抹去最后一位。
    }
    return ans;
}
void zh(long long a) {
    char zs[10001];
    int sum=0;
    while(a!=0) {
        zs[sum]=a%2;
        a/=2;
        sum++;
    }
    sum--;
    int js=sum;
    cd=sum;//转换为二进制后的最后一个元素的位置。如(10)
10
=(1010)
2
最后一个元素的位置为三。
    for(int i=0;i<=sum;++i)
    {
        e[js]=zs[i];
        js--;
    }
}

int main() {
    long long a,b;
    cin>>a>>b;
    zh(b);//将b转换为二进制。
    cout<<quickpow(a,e);
    return 0;
}
复制代码

 

代码:

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

PS:不用位运算的代码当指数为零时需要特判!

注意:因为是乘方运算所以很有可能会爆long long!

input:

2 11

output:

2048

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

&:‘&’叫做按位与。作用:把参与运算的两个数对应的二进制相与,只有对应的二进制均为1时,结果(应该也是二进制的形式)的对应位才为1,否则为0。

>>:'>>'叫做右移。作用:把“>>”左边的运算数的各二进制位全部右移若干位(“>>”右边的那个数)。

以此样例讲一下吧。

(11)10=(1011)2。

如何将二进制转换为十进制那?

酱紫,1*2+1*21 (+0*22) +1*23

∴211=2(1*2+1*21 (+0*22) +1*23)。

小学我们学过 an*am=an+m

∴211=21*22*28

快速幂就是这样计算的!

模拟一下样例:

ans=1,base=2。

11的二进制数为1011,不为0 进行循环直到为0。

1011的最后一位为1,ans*base。

若不为1,就不进行ans*base。

base*base,就是由2变成了4(2^2)。

1011抹去最后一位直到为0.

就是酱紫。

 

//转载来自这里


原文链接:https://www.cnblogs.com/skkyk/p/10872266.html
如有疑问请与原作者联系

标签:

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

上一篇:洛谷P3366【模板】最小生成树-克鲁斯卡尔Kruskal算法详解附赠习

下一篇:二分查找