Java语言实现快速幂取模算法详解

快速幂取模算法的引入是从大数的小数取模的朴素算法的局限性所提出的，在朴素的方法中我们计算一个数比如5^1003％31是非常消耗我们的计算资源的，在整个计算过程中最麻烦的就是我们的5^1003这个过程

缺点1：在我们在之后计算指数的过程中，计算的数字不都拿得增大，非常的占用我们的计算资源（主要是时间，还有空间）

缺点2：我们计算的中间过程数字大的恐怖，我们现有的计算机是没有办法记录这么长的数据的，所以说我们必须要想一个更加高效的方法来解决这个问题

当我们计算A^B％C的时候，最便捷的方法就是调用Math函数中的pow方法，但是有时A的B次方数字过大，即使是双精度的double也会溢出，这个时候为了得到A^B％C的结果，我们会选择使用快速幂取模算法，简单快速的得到我们想要的结果。

为了防止数字溢出并且降低复杂度，我们需要用到下面的公式:

a^b mod c = (a mod c)^b mod c

这个公式的意思就是：积的取余等于取余的积的取余。很容易看出来这个公式是具有传递性的，这样我们可以通过不断的取余让a越来越小，防止出现溢出的情况。

理论上，有了这个公式我们就可以写代码了，通过不断的对a进行取模保证结果不会溢出，这确实能计算出较大次方的幂的模，但是这种方法的复杂度仍旧是O(N)，并不快速。

为了更快速的计算出幂的模，我们还要依赖下面这个公式：

a^b mod c = (a²)^b/2 mod c , b为偶数
a^b mod c = ((a²)^b/2·a) mod c , b为奇数

这个公式很简单，原理就是不断的用a的平方来代替b，将b替换为原来的一半。因为我们通过第一个公式知道了一个数的模的相同次方的模相同（这句话说的有点绕，就是公式一的意思）。那么我们用a*a％c的结果来代替a效果是一样的。

所以根据上述的公式，我们得到复杂度O（logN）这样的计算快速幂的方法：

import java.util.Scanner;

public class Main {

public static void main(String[] args) {
 Scanner in = new Scanner(System.in);
 int a = in.nextInt(), b = in.nextInt(), c = in.nextInt();
 int res = 1;
 a ％= c;
 for (; b != 0; b /= 2) {
  if (b ％ 2 == 1)
   res = (res * a) ％ c;
  a = (a * a) ％ c;
 }
 System.out.println(res);
}
}

这个算法大概如此，第一步先a％=c是为了将a缩小一些，防止在for中第一次进行a*a的时候数字溢出。在for循环中，如果是b为奇数则令res=res*a，直接先将a乘到结果中去，最后做处理，又是为了防止数字溢出直接将res*a的结果mod c操作。这个for循环中，早晚有一天b会等于1，进入if分支，最后将res的值计算完毕mod c退出for循环，的到最后的结果。

来源：http://blog.csdn.net/quinnnorris/article/details/77587096