【学习笔记】快速幂

板块：数论
前置知识：C++语言基础、位运算
难度：极易

快速幂

快速幂是解决 $a^b\mathrm{mod}p$ 的问题的算法，有迭代版和递归版。在实际应用中，递归版往往需要花费更多的开销，所以迭代版会用的更多。

迭代版快速幂

迭代版快速幂分为三步：

• 如果 $b\&1$ 为真，则更新答案 $res=res\times a\mathrm{mod}p$
• 将 $b$ 右移一位
• 将 $a$ 反复做乘法，也就是 $a=a\times a\mathrm{mod}p$

    while (b) {
            if (b&1) {
                res = res * a % p;            
            }
            b >>= 1; 
            //b右移了一位后，a也需要更新
            a = a * a % p;
    }
1
2
3
4
5
6
7
8

递归版快速幂

递归版快速幂和迭代版快速幂的基本思路是一样的，只不过写法不一样。

int quickm (int a, int b, int p)
{
    if(b == 0) return 1;
    a %= p;
    int res = quickm(a, b >> 1, p);
    if(b & 1) return res * res % p * a % p;
    return res * res % p;
}
1
2
3
4
5
6
7
8