倍增法（英语：binary lifting），顾名思义就是翻倍。倍增法和二分法是“相反”的算法。二分法每次缩小为上一次的1/2，倍增法每次扩大一倍，两者都以2的质数减少或增加，它能够使线性的处理转化为对数级的处理，大大地优化时间复杂度。

“倍增”与“二进制划分”两个思想相互结合，降低了求解很多问题的时间与空间复杂度。快速幂其实就是“倍增”与“二进制划分”思想的一种体现。

数学知识储备：

一般地，在数学上，n个相同的因数a相乘的积记做$a^n$ 。这种求几个相同因数的积的运算叫做乘方，乘方的结果叫做幂。在$a^n$中,a叫做底数,n叫做指数。$a^n$读作“a的n次方”或“a的n次幂“。

指数幂的性质：

1. 同底数幂相乘，底数不变，指数相加。$a^m*a^n=a^{m+n}$即 (m,n都是有理数)。
2. 幂的乘方，底数不变，指数相乘。$(a^m)^n=a^{mn}$即 (m,n都是有理数)。

数的二进制表示（二进制划分）：
      $N=a_02^0+a_12^1+a_22^2+a_32^3+a_42^4+…$
   例如35，它的二进制是100011，第5、1、0位是1，即$a_5=a_1=a_0=1$，把这几位的权值相加，有$35=2^5+2^1+2^0=32+2+1$。
   数的二进制划分反映了一种快速增长的特性，第i位的权值$2^i$等于前面所有权值的和加1：
      $2^i=2^{i−1}+2^{i−2}+…+2^1+2^0+1$
   一个整数n，它的二进制表示只有$log^n$位。如果要从0增长到n，可以用1、2、4、…、2k为“跳板”，快速跳到n，这些跳板只有$k = log^n$个。
   倍增法的特点是需要提前计算出第1、2、4、…、2k个跳板，这要求数据是静态不变的，不是动态变化的。如果数据发生了变化，所有跳板要重新计算，跳板就失去了意义。

快速幂模板

求 m^k mod p，时间复杂度 O(logk)。

int qmi(int m, int k, int p)
{
    int res = 1 % p, t = m;
    while (k)
    {
        if (k&1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}