关于快速幂
关于快速幂
这次学习了下快速幂，所以来总结一下
快速幂，从字面意思就知道是快速的算出幂次方
我们先看试题a^b%m（快速幂取模）
a^b%m呢，如果靠死算的话不仅慢而且就连long long也会爆掉
所以就需要靠数学来总结个简单点的方法出来
下面是公式
这个公式一来就觉得很神奇（看不懂啊）还好，有推倒过程
具体点就是
a*b=(a1*m*b1*m)+(a1*m*b2)+(a2*b1*m)+(a2*b2)
又因为要mod m
所以带m的都为0
所以最后只剩下a2*b2
所以a*b%m=a2*b2%m
又因为a2=a%m,b2=b%m
所以最终就变为----->a*b%m=[(a%m)*(b%m)]%m
于是便有了
（然而这次是真的看不懂了，咳咳）
这是这个试题的方法
代码的话
试题看完了，就是真正的快速幂了
核心思想
代码的话
真正的快速幂也知道了，接下来就看看怎么让上面的快速幂取模更快吧
这样就完工了︿(￣︶￣)︿
Over