目录

快速幂取模的用途

快速幂取模的思路

快速幂具体分析

总结

在ACM这类竞赛中，可能会遇到指数型的数据取模问题，这个时候如果直接用int或者long long储存，就有可能会超出计算机整数的存取范围，而导致数据出错。所以我们需要一种方法进行计算。而这种方法就是我们这次要讲到的快速幂取模（简称快速幂）。这种算法在时间和空间上都做了尽可能的优化，所以学会之后，会觉得非常好用。

快速幂实现的最基本的理论就是我们离散课上或者数论中学过的一条公式推出的引理。引理：积的取余等于取余的积的取余。再在这条引理的基础之上，对指数型数据进行拆分以及合并，从而得到我们用的快速幂算法。本文我就不用例题讲解，直接对快速幂进行解析。毕竟快速幂的算法相对简单，而且适用题型较为一致。

对a^b进行分析。对于当a和b较小是直接用int或者long存是没有问题的，但是当a和b大到一定程度时，这就不是暴力存就可以解决的问题了。我们应该怎么去解决这个问题呢？

在这里我们需要把注意力放在“大”字上面，正是由于a和b过大才导致的问题。所以我们要想办法不断地减小a和b的规模，所谓逐个击破。根据上面的那条引理，我们知道了可以把指数拆开，从这个突破口突破。这里我们就不难想到这样一个算法：

当然有时候你可能会碰到用&的运算符的代码实现，其实和这个大致相同，只不过是用&操作符对b的奇偶性进行判断而已。&的操作符：二进制位中，1 & 1 = 1，其余组合均为0

附上用&实现的代码：

快速幂虽然是个“小”算法，但是有需要用到它的时候非常有用，所以不能小看它，只要稍加功夫去理解，快速幂还是很好学的，当然一切都需要你在题目中得到锻炼。