1.从简单的幂运算说起
对于一个接触过一门编程语言的人来说，幂运算是一个最基础的知识了，例如求2的20次方，我们只需要通过如下的代码即可完成
int res = 1;for (int i=0; i<20; i++){res *= 2;}
现在考虑一下这个问题，如果20再大点呢？ 200，20000，甚至……
当然，用循环可以解决，但是花费的时间却是以n的速度线性增长，n很大的时候，花的时间也是相当“可观” 。这里先插一句题外话 ， long long的最大值也就是2的64次方-1， 也就是说比这个数再大，基础类型就已经存放不下了，如果要求2的200次方，肯定会溢出，所以这里采取一个取模的运算，把最终的结果对1000取模，然后再输出 。
模运算
%就是取模的运算符，但如果像上面说的那样，运算完之后再取模，这是很不现实的，当你中间算到某个值的时候，就了，后面算的就都成了错的，为了避免这个问题，我们可以采用一个数学公式（对证明感兴趣的朋友可以百度）
(A*B)%M = (A%M * B%M) % M (%一般是写成mod，懂意思就行)
有了这个公式，我们可以在求幂的每一步都取模，这样就不会有溢出了
接下来我们看一个例子：
int ans = 1, num=2;for (int i=0; i<2000000000; i++){ans = ans%1000 * num%1000;//求2的二十亿次方}printf("%d\n", ans);
运行结果如下：
可以看出来，这花费的是时间还是相当长的，这对大型项目的影响还是很大的，很有必要提升效率！
2.快速幂
那么，为什么会花这么长的时间？肯定是由于循环的次数太多导致的 。
有没有什么办法减少循环的次数呢？
二十亿太大了，但我们就得想办法只循环一半次数，这样做的代价就是要将2平方，也就是底数变成了4；
啊！ 我们成功地把循环次数减少了一半，但十亿也还大，我们可以接着把4接着平方，变成16，循环次数又减少了一半……直到经过不断地平方求出了结果！
这就是快速幂核心的思想：二分法
当然，前面说的都是感性上的认识，接着我们用一个简单的例子严谨地考虑一下
比如：求2的10次方，
首先，把指数10折半，也就是要求4的5次方， 到这一步，发现5没办法再折半了，虽然2.5次方在数学上有意义，但是在编程上确是讲不通的 。这时怎么办呢？我们可以提出来一个4，变成4*4的四次方，保留左边的4，右边就可以接着折半；那，4的4次方又可以变成16的平方；接着16的平方变成256，别忘了之前提出来的4，结果就是1024.我们总共做了
2 * 2=4，4 * 4=16，16 * 16=256，256*4=1024
四次乘法，更严格的来说是logn次，这里n=10，那上面的2的二十亿次方，也取一下对数，大概是30次吧，这真的是太神奇了，！
好了，扯了这么多，该看看代码了，根据上面一步步地计算，我们不难发现一个规律，指数为奇数时，那个底数要提出来一个跟最后的结果相乘，然后进行折半偶数的时候直接进行折半 。折半的最终结果是指数变成1，
换一种说法，我们需要一个变量来保存最后的结果，在快速幂的过程中，如果指数是偶数，我们就先不用管，让它继续去折半(递归)，反正要的是最后的得数；如果是奇数的话，我们就需要去乘以这个底数（即提出一项），相当于一个保存的功能，因为这些提出的项，最后肯定也还要乘以到结果中的 。
根据上面的分析，我们来写一下代码
【1.从简单的幂运算说起】int quickPow(int x, int n, int mod)//O(logn){int ans = 1;//初始化while (n>0){if (1==n%2)ans = ans%mod * x%mod;//取模n /= 2;x = x%mod * x%mod;}return ans;}