快速幂

引入

如何求解

$a^{13}$怎么算，这个问题可能看着很简单，直接$aaa*…*a$就能算出来，但是如果这个指数如果变得非常大，比如$a^{100000}$ 这样写出来的代码运行起来就很慢,我们需要考虑优化。

先考虑$a^{2的幂}$

如果要求解$a^{64}$，我们可以发现$a*a$得到$a^2$再使用$a^2 * a^2$得到$a^4$，以此类推，我们可以花费很少的次数得到$a^{64}$。

推广

推广到正常数字，例如105。$a^{105}$,我们怎么去计算，我们可以知道$105 = 64 + 32 + 8 + 1$
于是我们可以得出$a^{105} = a^{64} * a^{32} * a^{8} * a^1$ ,再观察一下，发现每一个拆分出来的指数都是2的幂次，并且我们可以联想到二进制，$b(105) = 0110 1001$可以发现是对应的，也就是说我们可以把次数进行优化，并且从最低位到最高位依次累乘。

这边是快速幂的思想。

概念

快速幂算法是一种用于高效计算幂运算的算法。它通过将指数进行二进制拆分，并利用幂运算的性质，以减少计算的次数，从而提高运算速度。

算法原理

给定底数 a 和指数 n，要计算 a^n，快速幂算法的基本思想是将指数 n 二进制表示，并通过不断平方的方式来减少乘法的次数。例如，若要计算 a^13，可以按照以下步骤进行：

1. 将指数 13 转化为二进制：1101。
2. 根据二进制表示，计算 a^1，a^2，a^4，a^8。
3. 通过组合上述结果，得到 a^13 = a^8 * a^4 * a^1。

这样，只需进行四次乘法运算，而不是直接进行 a^13 次乘法运算，大大减少了计算的时间复杂度。

时间复杂度是$O(logn)$，也很好理解。

应用方式

1. 求幂运算

快速幂算法广泛应用于需要大量幂运算的场景，如密码学中的加密算法、图论中的邻接矩阵乘法等。

2. 模幂运算

在密码学领域，快速幂算法常被用于模幂运算，即 (a^b) mod m 的计算。这在很多加密算法中都是一个基本的步骤。

算法过程

1. 将指数 k 转化为二进制表示。
2. 从二进制表示的最低位开始，逐位检查：
   • 如果当前位是 1，则乘以当前的底数 base。
   • 无论当前位是否是 1，都将底数 base 进行平方操作。
3. 继续处理下一位，直到二进制表示的最高位。

//求 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;
}