基础数论--快速幂

正常求a^b的方法是迭代，但是效率太低，时间复杂度为O(n)

所以就有了快速幂的诞生

快速幂的基本思想是二进制。将指数用化为二进制表示，那么就只剩下logb + 1位，然后如果能够在小于O(logn)的时间复杂度内建立出一张2^0~2^(log b +1)的表的话，就能在O(log n)的时间复杂度内求出a^b

前人有了十分简便的写法

 1 typedef long long LL;
 2 int qmi(LL a,LL b,LL p){
 3     LL res=1;
 4     while(b){
 5         if(b&1){
 6             res=res*a%p;
 7         }
 8         b>>=1;
 9         a=a*a%p;
10     }
11     return res;
12 }