当前没有测试数据。

倍增

倍增法（英语：binary lifting)，顾名思义就是翻倍。它能够使线性的处理转化为对数级的处理，大大地优化时间复杂度。其基本思想是先通过成倍增长的方式求出状态空间上2的整数次幂项位置的值,再利用这些值组合为需要求解的答案。

指数幂：在数学中，把n个相同的因数a相乘，记做：$a^n$,通常求几个相同的因数相乘的运算叫做乘方，乘方的结果叫做幂，在$a^n$中，a叫做底数，n叫做指数，$a^n$读作 a的n次方 或者 a的n次幂

在C++中，有pow(a,b)函数可以实现a的b次方

幂运算的运算法则：

1、同底数幂运算，底数不变，指数相加

例如：$a^m*a^n = a^{m+n}$

$a^2 * a^4 = a^{2+4}$

2、幂的乘方运算，底数不变，指数相乘

例如：$(a^m)^n = a^{mn}$

数学中的倍增：

1->2->4->8->16->32->64->128$代表2^02^12^22^32^42^52^62^72^8$

如果要计算一个数a，就是$a^1$

倍增一次就是让a*a，即$a^{1} * a^1 = a^{1+1} = a^2$

再倍增一次就是让$a^2$自乘，即$a^{2} * a^2 = a^{2+2} = a^4$

再倍增一次，即$a^{4} * a^4 = a^{4+4} = a^8$

通过这样的倍增规律，如果要求$a^{128}$,就只需要倍增6次即可实现

如果求$a^{100}$？

这样我们就需要用到快速幂的思想，所谓的快速幂是通过二进制快速计算出来一个数的幂运算

我们可以先写出100的二进制：1100100

然后再把他的转换过程列举出来

$a^{100} = a^{64} * a^{32} * a^{4} = a^{64+32+4}$

64+32+4=100，获得幂值

求$a^{100}$,我们就可以看成：$a^{100} = a^{4} + a^{32} + a^{64} = a^{4}*a^{32}*a^{64}$

由此可得，计算快速幂，实际就是找为1的二进制结果，将结果相乘即可

利用快速幂：计算$a^b$的结果

int fast_pow(int a,int b){
  int ans = 1;
  while(b){
    if(b&1){ // 当前二进制位为1
    	ans = ans*a; 
    }
    a = a*a;
    b >> = 1;
  }
  return ans;
}

利用快速幂：计算$a^b \% m$的结果

int quick_pow_mod(int a, int b, int m) {
    int ans = 1;
    int base = a % m;
    while (b) {
        if (b&1) { // 当前二进制位为1
            ans = (ans * base) % m;
        }
        base = (base * base) % m;
        b >> = 1;// 右移一位，相当于n除以2
    }
    return ans;
}

完成下面任务：

a的b次方

a的b次方%m