[复习]快速幂算法

　　快速幂基于分治，同底幂数的乘法：$a^{m} imes a^{n} = a^{m + n}$。所以我们可以得到$a^{n} = a^{frac{n}{2}} imes a^{frac{n}{2}}$，看起来好像没有错。不过不要忘了，我们的快速幂貌似不怎么支持一个数的小数次幂。

所以需要进行讨论:

$a^{n} = left{egin{matrix}a^{frac{n}{2}} imes a^{frac{n}{2}} left ( 2mid n ight )\ a^{left lfloor frac{n}{2} ight floor} imes a^{left lfloor frac{n}{2} ight floor} imes a left ( 2 mid n ight )end{matrix} ight.$

照这样下去，是不是准备栈溢出？

赶快把边界补上 a (x == 1)

细心地话可以吧 1( x == 0 && a != 0)

1 long long _pow(int a, int pos){
2     if(pos == 1) return a;
3     if(pos % 2 == 1) return (_pow(a,pos/2)*_pow(a,pos/2)*a);
4     return (_pow(a,pos/2)*_pow(a,pos/2));
5 }

不过_pow(a,pos/2)是不是已经算过了对不对？但是电脑是个忠实的执行者

只管执行，相当于拖慢了速度，这速度还是很恐怖的,原本的$Oleft(log n ight)$的时间复杂度

被这么一玩，跟for一比，貌似没有优化太多，反而多了调用和返回的时间

于是，我们重新改改：

1 long long _pow(int a, int pos){
2     if(pos == 1) return a%n;
3     long long temp = _pow(a,pos/2);
4     if(pos % 2 == 1) return ( temp * temp*a)%n;
5     return ( temp * temp )%n;
6 }

拿出去溜溜，是不是快多了？