算法：

 1 int qmi(int a, int b, int mod)
 2 {
 3     //答案
 4     int res = 1;
 5     //乘数
 6     int mul = a;
 7     while (b)
 8     {
 9         //在二进制下b的第0位是否是1
10         //是1则要乘,否则不要
11         if (b & 1)
12             res = res * 1LL * mul % mod;
13         mul = mul * 1LL * mul % mod;
14         b = b >> 1;
15     }
16     return res;
17 }

原理：

《应用》

比如当n为1e9,单纯地使用快速幂还不够，还有用二分递归：