（1）快速幂

原理：将指数转化为二进制表示，指数不断右移，base不断倍增，如果这一位是1则ans乘以base，否则不乘。

e.g.    

代码：

template<class T> //模板化，方便代码重用 T qpow(T a,int b) { T ans=1,base=a; while(b) { if(b&1) { if(b&1) ans*=base; base*=base;//倍增，变为a^2,a^4,a^8 b>>=1;//右移 } } return ans; }

 

时间复杂度：O(log n)