如果
a，
b和
c都是整数，实现可以进行通过更高效的二进制幂和减少模
c中的每一步，包括第一次（即降低
a模
c，你甚至开始之前）。这确实是实现的目的
long_pow()。该函数具有两百多行代码，因为它必须处理引用计数，并且它处理负指数和许多特殊情况。
尽管从本质上讲，算法的思想很简单。假设我们要计算
a ** b正整数
a和
b，并且
b具有二进制数字
b_i。然后，我们可以写
b为
b = b_0 + b1 * 2 + b2 * 2**2 + ... + b_k ** 2**k
答
a ** b如
a ** b = a**b0 * (a**2)**b1 * (a**2**2)**b2 * ... * (a**2**k)**b_k
该产品中的每个因子均为形式
(a**2**i)**b_i。如果
b_i为零，我们可以简单地忽略该因子。如果
b_i为1，则系数等于
a**2**i，并且可以
i通过反复平方来计算所有这些幂
a。总体而言，我们需要乘以平方和乘以
k，其中
k是的二进制数
b。
如上所述，因为
pow(a, b, c)我们可以
c在平方和乘法之后的每一步中减少模数。
