快速幂

快速幂，可以优化指数计算，将朴素的 $O(n)$ 的时间复杂度优化到 $O(\log n)$

原理是，将幂通过二进制拆分，只需要计算拆分后的值，就能组合出完全幂的答案

举例如下：有 $a^{14} = a^{1110_{(2)}} = a^{1*2^3}*a^{1*2^2}*a^{1*2^1}*a^{0*2^0}$

又有 $a^{2^i}=a^{2^{i-1}}*a^{2^{i-1}}$ ，于是我们可以倍增地计算指数积的因子，代码可以这样来实现

• 二进制拆分幂

while (b)//当b的十进制不为0时，即二进制不全为0时
{
    if (b & 1){//按位与1，取出二进制的末尾值,
        ......//操作过程
    }
    b >>= 1;//向右移一位
}

• 倍增计算因子

while (b)
{
    if (b & 1) res *= a;//如果取出来的二进制末尾值为1，则将返回值乘上这个因子
    a *= a;//a倍增
    b >>= 1;
}

• 最后返回指数计算答案即可

推广到一般情况，快速幂也可以应用到任意满足结合律的计算中，例如取模运算，矩阵乘法

即满足 $(x*y)*z = x*(y*z)\ \ \forall x,y,z$ 的运算成立

以洛谷P1226 取模运算为例：对于取模运算，这样两个等式显然成立

$(a*b)(mod)p=\{ a(mod)p*b(mod)p\}(mod)p$

$(a+b)(mod)p=\{a(mod)p+b(mod)p\}(mod)p$

可以推出以下变形：$a^b (mod) p = \{ a^{i_1}(mod)p*a^{i_2}(mod)p*...*a^{i_k}(mod)p \}(mod)p,\sum_i^k=b$

所以，可以对标准的快速幂函数内进行部分修改，满足上述的等式

long long quickpower_p(long long a, long long b, long long p) {
    long long res = 1;
    while (b)
    {
        if (b & 1) res = res * a % p;//每个因子都对p取余
        a = a * a % p;//倍增因子同样需要对p取余
        b >>= 1;
    }
    return res;
}

该题完整代码：

#include <iostream>
using namespace std;

long long a, b, p;

long long quickpower_p(long long a, long long b, long long p) {
    long long res = 1;
    while (b)
    {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

int main()
{
    cin >> a >> b >> p;
    cout << a << '^' << b << " mod " << p << "=" << quickpower_p(a, b, p) << endl;
    return 0;
}