之所以知道有快速幂这个东西，是因为之前在做题的时候刚好碰到的大数的幂运算。算法讲究的是用尽量小的内存和尽量短的时间解决问题，所以如果只用平常的方法计算，势必会超内存和超时。

学了一段时间的算法，决定开始写博客记下来，可以加深自己对该算法的理解。
在讲快速幂之前，先引入幂运算的一个公式：

同底数幂相乘，底数不变，指数相加。
这是高中or初中就知道的一条公式，在快速幂中，a的b次方可以看成a的x次方与a的(b-x)次方相乘，进一步又可以将b拆分成多个数相加然后再计算。

此时，又要引入一个知识点：二进制
b的二进制可以写成由0和1构成的，即b=0（或者1） （2^i）+….也就是说，上面提到的x就是2的i次方与0或1相乘，所以计算的时候是要对b的二进制位上全部数字进行遍历。根据0与任何数相乘都为0，而且任何数的0次方都为1，在累乘情况下是没有影响的，所以当二进制位的数为0的时候，可以不去计算，只关注二进制位上的数为1时就可以。
即 a^b = a ^ ( (2^i) 1 + ….. )
= a ^ ( (2^i) 1 ) a ^ ( (2^i1) 1 ) ……
= a ^ (2^i) \ a ^ (2^i1) \ ……

现在来解决2^i…
举个例子，5的二进制为101，即5 = 2^21+ 2^10 + 2^01。在不去掉0的情况下,假设bi代表的是二进制位上的1或0，
a^b = a^((2^0)b0) a^((2^1)b1) a^((2^2)b2)…..
分离出每个乘数，设A0=a^((2^0)b0)，A1=a^((2^1)b1)，A2=a^((2^2)b2)，先不看bi，即A0=a^(2^0),A1=a^(2^1),A2=a^(2^2),会发现，A1是A0的平方倍，A2是A1的平方倍。
也就是说，在遍历二进制位的全部数的时候，a = aa，逐步递推，就可以不用考虑2^i，只是在计算时考虑bi是0还是1，要不要把这个数算进总得数而已。

最后，再引进一条公式：

(ab)%c=(a%c)(b%c)%c
为什么要%C，是因为这样做可以减小a的数，取最后大数中的后面几个数来计算，不至于数字过大而超时超内存，而且也不会影响结果。

综上，写成JAVA代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 //求a^b，c用来缩小范围
public static int quick(int a,int b,int c){

    int sum = 1;//记录最终得数
    a = a%c;//只需要最后几位就可以了
    while (b>0){

        if ((b&1)==1){
            //该数的二进制数的最后一位为1时才计算
            sum = (sum*a)%c;
        }

        b >>=1 ;//主要是遍历b的二进制位的全部数字，这样是往前一个
        a = (a * a)%c;//因为后一个乘积是前一个的平方倍。

    }

    return sum;
}

学完知识就开始运用啦
hdu:2035 人见人爱A^B:”http://acm.hdu.edu.cn/showproblem.php?pid=2035“

附上我的ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.util.*;
public class Main {

    public static void main(String[] args) throws IOException {

        Scanner scanner = new Scanner(System.in);

        while (true){
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            if (a!=0 && b!=0){
                System.out.println(quick(a,b,1000));
            }
            else {
                return;
            }
        }

    }

    //求a^b，c用来缩小范围
    public static int quick(int a,int b,int c){

        int sum = 1;//记录最终得数
        a = a%c;//只需要最后几位就可以了
        while (b>0){

            if ((b&1)==1){
                //该数的二进制数的最后一位为1时才计算
                sum = (sum*a)%c;
            }

            b >>=1 ;//主要是遍历b的二进制位的全部数字，这样是往前一个
            a = (a * a)%c;//因为后一个乘积是前一个的平方倍。

        }
        return sum;
    }
}

在学快速幂的时候看了很多博客，对我帮助比较大的是：http://blog.csdn.net/ltyqljhwcm/article/details/53043646