问一道算法题，求思路
描述给定整数a,b,n,要求计算(a^b)mod n输入多组数据,每组数据一行,为三个用空格隔开的整数a,b,n1<=a<=5000,0<=b<=10^8,1<=n<=5000000输出每组数据输出一行,为所求值样例输入2 3 52 2 4样例输出30
//反复平方法,求a^b mod n 的值,<算法导论>539页//解释一下a^b mod c：//a^b mod c=a^(f[0]*2^0+f[1]*2^1+f[2]*2^2...f[t]*2^t)//因为 a*b mod c= ((a mod c) *b) mod c//所以//a^b mod c=(((f[0]*2^0 mod c)*f[1]*2^1 mod c)......*f[t]*2^t mod c)//用这种方法解决a^b mod c 时间复杂度//2^t<=b<2^(t+1)//t<=log(2)b<t+1//因为 b是个整数 所以//t=log(2)b//时间复杂度比直接循环求a^b大大的降低了////模取幂运算 //事实上，m^e mod n可以直接计算，没有必要先算m^e。 //m^e mod n叫做模取幂运算，根据简单的数论知识，很容易设计一个分治算法。具体如下: //设<b[k], b[k-1],...,b[1],b[0]>是整数b的二进制表示（即b的二进制有k+1位，b[k]是最 高位）//下列过程随着c的值从0到b成倍增加，最终计算出a^c mod n ////Modular-Exponentiation(a, b, n) //1. c ← 0 //2. d ← 1 //3. 设<b[k],b[k-1],..b[0]>是b的二进制表示 //4. for i←k downto 0 //5. do c ← 2c //6. d ← (d*d) mod n //7. if b[i] = 1 //8. then c ← c + 1 //9. d ← (d*a) mod n //10. return d ////首先说明一下，上述伪代码中用缩紧表示语句之间的层次关系，例如第5~9行都是for循环体 //内的语句，第8~9行都是then里面的语句。这是我比较喜欢的一种表示方法 ；） //上述伪代码依次计算出的每个幂或者是前一个幂的两倍，或者比前一个幂大1。过程依次从 //右到左逐个读入b的二进制表示已控制执行哪一种操作。循环中的每次迭代都用到了下面的 //两个恒等式中的一个： //a^(2c) mod n = (a^c mod n)^2 //a^(2c+1) mod n = a * (a^c mod n)^2 //用哪一个恒等式取决于b[i]=0还是1。由于平方在每次迭代中起着关键作用，所以这种方法 //叫做“反复平方法(repeated squaring)”。在读入b[i]位并进行相应处理后，c的值与b的 //二进制表示<b[k],b[k-1],..b[0]>的前缀的值相同。事实上，算法中并不真正需要变量c， //只是为了说明算法才设置了变量c：当c成倍增加时，算法保持条件d = a^c mod n 不变，直 至c=b。 public long ModularExponent(long a,long b,long n){ int c=0; long d=1; int binary[]=new int[32]; int index=0; while(b!=0) { if((b&1)==1) binary[index]=1; else binary[index]=0; index++; b>>=1; } index--; for(int i=index;i>=0;i--){ c=2*c; d=(d*d)%n; if(binary[i]==1) { c=c+1; d=(d*a)%n; } } return d; }