刚刚接触算法的初学者第一次记录关于算法的理解，如果有什么不正确的地方各位大佬请指正。
最开始遇到一些关于求a^n次方取模的题目最开始的我想法无非是（可能是我比较笨）一次次的乘过去了
如下所示：
1 int a,b,mod,ans=1; 2 cin>>a>>b>>mod; 3 for(int i=1;i<=b;i++) 4 { 5 ans=ans*a; 6 } 7 cout<<ans%mod<<end;
但是想法仅仅是个天真的想法而已 比如如果要求9^1234次方这种算法太过于消耗时间
还有就是计算机最后也不一定放得下这个答案 所以一般这种题目都有取模的要求 虽然我这个地方按照思路来最后答案也取模了 但是可能在乘的过程中这个答案就溢出了..
所以首先我们要知道关于取模的运算 如下的公式是成立的
(a * b) % mod = (a % mod * b % mod) % mod
(a + b) % mod = (a % mod + b % mod) % mod
然后我们再来说快速幂的核心思想
如果我们要求2^7按照我以前的思维就是 ans=1*7*7*7*7*7*7*7 但是他的时间复杂度是O（n）
我们一般手算这种东西都是比较小的所以感觉不到 但是题目一般都是不会让你这么好过的 1000ms的时间限制摆在那里。。
所以我们可以知道 2^7我们可以拆成 2^7=2^4*2^2*2^1 这样是不是发现就只要计算三次了呢！
如果这个不明显我们可以看看2^63按照一般方法我们要计算65次，但是2^63=2^32*2^16^2^8^2^4*2^2*2^1 这样只计算了6次！ 差别就明显了
现在我们就要想办法如何实现这个过程了 我们可以发现其实我们是把指数看成了二进制数
7=111 63=111111 我们要判断指数在二进制的时候 每一位上是否为1 就知道是否要乘了
比如2^5 5的二进制为101 也就是只需要2^5=2^4*2^1就可以了 因为中间是0 所以我们不用乘2^2
这个地方我们要判断指数的二进制每一位是否为1
我们可以很快的想到用&（按位与）运算符 如果&1等于1的话就说明最右边这一位是1了
那么如果我们判断完这一位之后 这一位肯定就不需要再判断了 我们得舍去他 我们也能很快想到用>>（右位移）运算符 把7>>1 其实就是（111>1）当然就变成11了
当每一位都判断完后 这个指数每一位也都被右移了 当然最后就变成了0 也就是运算完成了！ 下面上代码理解。
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 int quickchen(long long a,long long b,long long mod) 5 { 6 long long ans=1; //ans用来存放最终答案 注意是乘法运算 所以初始化的值应该是1 7 8 while(b) //这个地方就是我们的指数 按照上面的想法 如果这个数为0了也就是位移完了 答案也就出来了 循环就可以结束了 9 { 10 if(b&1) //判断最右位是否是1 11 12 ans=(ans*a)%mod; //如果是1 那么这一位就应该乘上 13 //注意这里两个取模 都应该乘了之后再取模 而不是ans*=a%mod; 如果是这样 那其实是ans=ans*a%mod；
//按照上面我列出来的取模公式 这就不对了 15 a=(a*a)%mod; //注意这句话 是不需要写在判断里面的 就比如2^5=2^4*2^1（5的二进制数是101）第二次循环时候那一位是不需要乘上的 16 //但是下一次你使用的是2^4而第一次乘的时候a是2^1次方
//所以第二次不管需不需要乘 这个a都应该乘以自己变成2^2以便下次使用 17 18 b>>=1; //指数右移一位 19 } 20 return ans%mod; 21 } 22 23 int main() 24 { 25 long long a,b,mod,sum; //a^b次方 mod模数 sum是求模后结果 26 cin>>a>>b>>mod; 27 sum=quickchen(a,b,mod); //调用自定义的快速幂函数 28 cout<<a<<"^"<<b<<" mod "<<mod<<"="<<sum; 29 return 0; 30 }
讲到这里快速幂算法就讲完了 他的时间复杂度是O（logn） 是不是快了许多！
当然其实我也只是会用了而已 按照我自己的脑子是想不出来这种东西的（菜）
如果大佬看见觉得哪里很可笑希望能指教我 毕竟我也是初学容易忘 只是记录下自己的思路
下一篇博客我会在这个基础上写一个关于矩阵快速幂的算法理解（其实自己也不太理解 只能写下来给自己看了）
- 还没有人评论，欢迎说说您的想法！
客服
