关于快速幂

关于快速幂

这次学习了下快速幂,所以来总结一下

快速幂,从字面意思就知道是快速的算出幂次方

我们先看试题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