说实话，自己是第一次接触到快速幂这种东西，觉得有必要记录下来。

题意：

计算a^n % b，其中a，b和n都是32位的整数。

样例：

例如 2^31 % 3 = 2例如 100^1000 % 1000 = 0

挑战：

O(logn)

1.解题思路

  在介绍这个题的解题思路之前，我先来简单的介绍一下，什么是快速幂？

(1).快速幂

  快速幂，顾名思义就是快速的求次幂，例如:a^b，普通的算法就是累乘，这样的计算方法的时间复杂度就是O(n),而快速幂的方法使得次幂的计算方法的时间复杂度降低到O(logn).
  假设我们要求a^b的结果，这里我们可以将b转换为二进制来求。例如：

                    a^11 = a(2  ^ 0 + 2 ^ 1 + 2 ^ 3) = a ^(1011);

  所以，我们得出结果：a^11 = (a ^ (2 ^ 3)) *( a ^(2 ^ 1)) *( a^(2 ^ 0));
也就是说，我们只要把次幂化成二进制数，那么我们操作起来就非常的简单了。怎么化成二进制呢？在位运算符中，>>符号表示将一个数字右移一位，也就是说，我们这里可以通过这个符号来一位一位的计算(这里讲的是二进制数，当十进制数使用这个符号来操作的话，我们可以将十进制数当成二进制数右移)。同时我们还可以使用&符号来看看我们二进制数的最后一位数是不是0，比如 a & 1 == 0,表示的是a的二进制数的最后一位是0，反之就是不为0.这里清楚了这一点的话，下面的代码就非常的容易理解。
  这里我来举一个例子，例如，我们想要求a ^ b的结果，按照快速幂的求法，代码如下：

public int fastPower(int a, int b) {        int ans = 1;        int base = a;        while (b != 0) {            if ((b & 1) != 0) { //如果当前的次幂数最后一位(二进制数)不为0的话，那么我们将当前权值加入到最后答案里面去                ans = ans * base;            }            //权值增加            base = base * base;            b >>= 1;        }        return ans;    }

(2).取模

  但是这个题不是简单的快速幂，而是需要求余数，理解到了上面的快速幂的求法，那么这里就非常的简单，就是在计算的时候在取一次模就行了。

public int fastPower(int a, int b, int n) {        if (n == 0) {            return 1 % b;        }        long ans = 1l;        long base = a % b;        while (n != 0) {            if ((n & 1) == 1) {                ans = (ans * base) % b;            }            //为了避免超出long的范围，所以取三次模            base = (base % b) * (base % b) % b;            n >>= 1;        }        return (int) ans;    }

原著是一个有趣的人,若有侵权,请通知删除