题目描述：

给a,b,c三个数字，求a的b次幂对c取余。

数据范围：多组样例循环输入，每一组输入a,b,c (1<=a,c<=10^9,1<=b<=10^1000000)。

输入：

2 2 2
139123 123124121241452124412124 123121

输出：

8984

1、首先我们先定义大数变量

BigInteger a,b,c;

2、然后输入大数

a=input.nextBigInteger();
b=input.nextBigInteger();
c=input.nextBigInteger();

3、之后就是快速矩阵幂算法了

　　快速矩阵幂就是用二进制来求幂的方法。在说快速矩阵幂之前，我们先看一个例子：A^23 = A^16 * A^4 * A^2 * A。16、4、2、1正好对应的就是23的二进制，即10111。

　　当我们计算A^2的时候可以通过A*A来获得；当我们计算A^4的时候，可以通过A^2 * A^2获得；同理我们可以通过A^8 * A^8来得到A^16。这就是快速矩阵幂的思想，复杂度从O(n)降到了O(logn)。

　　运算过程如下：

　　（用temp记录当前幂的值）当位数==1时，temp*=A，且A=A*A，此时temp=A，A==A^2；

　　继续第二位也==1，继续temp*=A，且A=A*A；此时temp=A^3，A==A^4；

　　继续第三位也==1，继续temp*=A，且A=A*A；此时temp=A^7，A==A^8；

　　第四位！=1，继续A=A*A；此时temp=A^7，A==A^16；

　　继续第五位==1，继续temp*=A，且A=A*A；此时temp=A^23，A==A^32；

　　之后退出循环，返回结果temp。

　　以上只用了5次循环，远远小于23次。

完整代码

 1 import java.math.*;
 2 import java.util.*;
 3 public class Main {
 4 
 5     public static BigInteger POW (BigInteger a,BigInteger b,BigInteger c)
 6     {
 7         
 8         BigInteger ans = BigInteger.valueOf(1);//  大数 1
 9         BigInteger TW=BigInteger.ONE.add(BigInteger.ONE);// 大数 2
10         while(!b.equals(BigInteger.ZERO))//如果b != 0  进入循环
11         {
12             if(b.remainder(TW).equals(BigInteger.ONE)) //  如果该位==1，则ans=ans*a;
13                 ans = (ans.multiply(a)).remainder(c);//
14             b=b.divide(TW);// 为了下一步计算b二进制的下一位
15             a = (a.multiply(a)).remainder(c);// a*a 相当于A * A 或者 A^2 * A^2 等等
16         }
17         return ans;//返回
18     }
19 
20     
21     public static void main(String[] args) {
22         // TODO Auto-generated method stub
23         Scanner input = new Scanner(System.in);
24         BigInteger a,b,c;
25         while(input.hasNext()){
26             a=input.nextBigInteger();
27             b=input.nextBigInteger();
28             c=input.nextBigInteger();
29             System.out.println(POW(a,b,c));
30         }
31 
32     }
33 
34 }

总结

不做不知道，一做吓一跳，水平太低了，要好好练习了。

欢迎大家指正。