c++ - 幂后取模算法

Question

下面一段代码计算a^b%c的值，

int powermod(int a,int b,int c)
{
    int ans = 1;
    while(b)
    {
        if(b&1)
            ans=(ans*a)%c;

        a=(a*a)%c;
        b=b>>1;
    }
    return ans;
}

我试图理解代码背后的算法，但无法理解。有人可以帮我解释一下吗？这是如何工作的，它背后的算法有名字吗？

Answer 1

如果没有“模 c”部分，则更容易看到发生了什么:

int power(int a,int b)
{
    int ans = 1;
    while(b)
    {
        if(b&1)
            ans *= a;
        a=a*a;
        b=b>>1;
    }
    return ans;
}

这是计算 a^b 的标准算法，每次考虑 b 一位，从最低有效位开始。对于 b 的每一位，如果它是 1，则将答案乘以 a 的当前值。然后，要移动到下一位，对 a 进行平方并将 b 向右移动 1 位。该算法的理论是 x^{2m + 2n} = x^2mx²ⁿ.

这种算法称为 "exponentiation by squaring" 、“平方和乘法”或“二进制求幂”。

发布的算法(在评论中指出的更正后)以 c 为模做同样的事情，使用 (x*y)%z == ((x%z ) * (y%z)) % z (也就是说，模运算既可以应用在乘法之前，也可以应用在乘法)。它使用它来保持 a 小于 c，尽管重复平方。