如果你不知道快速幂有多么快，那我可要告诉你这样一句话：
快速幂之于乘法的作用，相当于乘法之于加法的作用。
直接对比说明：
//101+101+101+101+101+101+101+101+101+101 加法算式
//101*110 乘法算式
//列竖式：
// 101 乘数1
// * 110 乘数2
// -----------
// 000 ← 0*(101*1) 0*(101)
// 101~ ← 1*(101*10) 1*(101+101)
// 101~~ ← 1*(101*100) 1*(101+101+101+101)
// -----------
// 11110
//显然，我们算了三个数（向左箭头），这三个数刚好是乘数2的一个位数
//第i个箭头对应的数是乘数1左移位i次再乘上乘数2的第i位得到
//第i个箭头里括号里的数非常好递推，只要第i-1的括号里的数再左移一次就好
//如果认为位移一次的代价是1，累加一个数的代价是1
//那么总代价就是2*(乘数2在二进制下的位数)
//即2*log(乘数2)//101*101*101*101*101*101*101*101*101*101 乘法算式
//101^110 乘方算式(姑且拿异或符号当乘方来用，你懂就好)
//列式：
// 101 底数
// ^ 110 幂
// -----------
// 000 ← 0*(101^1) 0*(101)
// 11001? ← 1*(101^10) 1*(101*101)
// 1001110001 ← 1*(101^100) 1*(101*101*101*101)
// -----------
// 1010001010
//显然，我们算了三个数（向左箭头），这三个数刚好是幂的一个位数
//第i个箭头对应的数是底数做平方i次再乘上幂的第i位得到
//第i个箭头里括号里的数非常好递推，只要第i-1个括号里的数再平方就好
//如果认为算一次平方的代价是1，累加一个数的代价是1
//那么总代价就是2*(幂在二进制下的位数)
//即2*log(幂)
其原理就是这样。
实现的话，如果你是个新手，没写过快速幂，你可以考虑开一个辅助数组，然后存底数，底数的平方，底数的平方的平方，etc..
整完之后在乘个位数。
如果你熟练一点，就不必开辅助数组了。
不高兴的话，你套板子也行。