直播平台网站建设,网站分享链接怎么做,wordpress登录界面图标,电子商务网址大全快速幂
如果我们打算求a^b, 我们可能会写一个for循环#xff0c;乘以b次a#xff0c;时间复杂度为O(b)
当b比较小的时候还可以运用#xff0c;但是当b很大#xff0c;比如b1000000,此时时间复杂度就显然很高了#xff0c;我们需要对其进行优化 ———快速幂
开始之前乘以b次a时间复杂度为O(b)
当b比较小的时候还可以运用但是当b很大比如b1000000,此时时间复杂度就显然很高了我们需要对其进行优化 ———快速幂
开始之前先说两个前置知识
1 二进制构成数字
众所周知每个十进制数都可以由唯一的二进制数表示
例如13的 二进制表示为 1101 即表示为 1*2^3 1*2^2 0*2^1 1*2^0即13可以由841组成
我们不难发现每一个十进制数都由其对应的二进制数那么每一个十进制数都可以有1 2 4 8 32 64 … 等这种二的次方数相加得到并且每一种数只能取1个或0个
再例如 9其二进制为1001 819 即由1个8和1个1相加得到9
2 位运算 运算符可以直接对二进制进行操作1 1 11 0 0 0 1 0 0 0 0
我们不难发现只有11才是1根据这个思想我们可以判断当前数字的二进制是否有1 右移运算符可以删掉末尾二进制数例如5 的二进制为101 51 2 2的二进制为10 删掉了原先末尾的1再例如6的二进制为110 613 3的二进制为11 删掉了末尾的0其实不难发现右移1就是乘以2n,就是乘以2^n次方
结合和
我们可以写个循环。逐渐判断每一位是否是1
int b 13;
int res 0;//统计b二进制1的数目
while(b){if(b11)res; //如果当前位为1就统计1b b1;//将末尾位删掉
}3 快速幂算法(不取余版)
学完前面两个前置知识我相信再学习 快速幂 将会很简单
首先假设我们要求5^13次方
13的二进制为1101 所以13 841
即5^13 5^1 * 5^4 * 5^8
ps: 幂运算可是高中数学学的 a^(mn a^m * a^n;
有这些知识我们就能直接看代码了
要是还有疑惑点看代码注释也能看懂
long long quick_pow(long long a,long long b){//计算a^b次方long long res 1;//用res保存答案//当b变成0后就可以停止循环了while(b){if(b 1) ans*a;//如果b当前二进制为1就要乘上这个数b1; //将b末尾的二进制数删掉a*a; // 将a乘以自己进行翻倍//比如开始a5,接下来a 5^2,a5^4,a5^8,a5^16....//通过遍历每个在范围内的2的次方数来更新a}
}4 取模版快速幂
快速幂只有五行代码是不是很简单呢
不过别急上面的快速幂是最原始版的一般不是很常用当a本身非常大时如果a*a可能 long long 都给爆掉了所以我们一般会采取取模的方式进行运算
前置知识 (a *b *c *d )%p (((a *b)%p *c)%p *d)%p
即每次乘以下个数前可以先取模这样最后答案不变所以我们的代码可以进行优化了
LL quick_pow(LL a, LL b, LL p){ //LL是long long 的缩写//p是要对取模的数字LL ans 1;while(b){if(b 1)ans (ans*a)%p;b 1;a (a*a) % p;}return ans;}原题链接875. 快速幂 - AcWing题库
完整代码
#includeiostreamusing namespace std;
typedef long long LL;
LL n;
LL quick_pow(LL a, LL b, LL p){LL ans 1;while(b){if(b 1)ans (ans*a)%p;b 1;a (a*a) % p;}return ans;}
int main(){cinn;while(n--){LL a,b,p;cinabp;coutquick_pow(a,b,p)endl;}return 0;
}
