快速幂的目的就是做到快速求幂，假设我们要求a^b,按照朴素算法就是把a连乘b次，这样一来时间复杂度是O(b)也即是O(n)级别，快速幂能做到O(logn)，快了好多好多。它的原理如下：

　　假设我们要求a^b，那么其实b是可以拆成二进制的，该二进制数第i位的权为2^(i-1)，例如当b==11时

　　　　　　　　　　　　a11=a(2^0+2^1+2^3)
　　11的二进制是1011，11 = 2³×1 + 2²×0 + 2¹×1 + 2º×1，因此，我们将a¹¹转化为算 a2^0a2^1a2^3，也就是a1a2a8 ，看出来快的多了吧原来算11次，现在算三次，但是这三项貌似不好求的样子....不急，下面会有详细解释。 　　由于是二进制，很自然地想到用位运算这个强大的工具：&和>> &运算通常用于二进制取位操作，例如一个数 & 1 的结果就是取二进制的最末位。还可以判断奇偶x&1==0为偶，x&1==1为奇。 >>运算比较单纯,二进制去掉最后一位

代码演示

def op(a, b, p):
    s = 1
    a = a % p
    while b > 0:
        if b & 1:  # 取二进制的最末位
            s = (s * a)
        b >>= 1  # 去掉二进制的最末位
        a = (a * a)
        print(s, a)
    return s % p


a, b, p = map(int, input().split())

s = op(a, b, p)

print(f"{a}^{b} mod {p}={s}")

代码解释

函数 op(a, b, p) 的详细解释如下：

s = 1：初始化结果变量 s。在快速幂算法中，s 将累乘每一步的计算结果。

a = a % p：先对 a 进行模运算，确保 a 的值不会因为连续乘法而变得过大。这也有助于提高计算的效率。

while b > 0：这个循环会持续运行，直到 b 减少到 0。在每一步中，算法都会根据 b 的当前最低位是 0 还是 1 来决定是否需要将当前的 a 值乘到结果 s 上。

if b & 1：这个条件判断用于检查 b 的最低位是否为 1（即判断 b 是否为奇数）。如果是，那么根据快速幂算法的规则，需要将当前的 a 乘到 s 上。

s = (s * a)：如果 b 的当前最低位为 1，那么将当前的 a 值乘到 s 上。

b >>= 1：将 b 右移一位，相当于将 b 除以 2 并向下取整。这一步操作是为了在下一次循环中处理 b 的下一个二进制位。

a = (a * a)：将 a 自乘，为下一步的迭代准备。这是因为每当 b 右移一位时，对应的 a 应该是其平方。

print(s, a)：在循环中打印当前的 s 和 a 的值，这一行主要用于调试和观察算法的执行过程，了解 s 和 a 的变化。

return s % p：最后，返回 s 对 p 取模的结果。即便在循环中 s 已经进行了模运算，最终结果仍然需要对 p 取模以确保正确性。

整个函数体现了快速幂算法的精髓：通过将指数
b 分解为二进制表示，并只在二进制表示中的位为 1 时累乘对应的基数
a 的幂，有效减少了计算量。通过每次迭代将 a 平方，并根据 b 的当前位是否为 1 来决定是否乘到 s 上，算法以对数时间复杂度完成了原本可能是线性时间复杂度的计算。