如果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在平方和乘法之后的每一步中减少模数。