Java实现快速幂算法详解

快速幂算法（Power Mod）可用来求解形如$a^b\%c$的表达式，其中$a$、$b$和$c$均为正整数。快速幂算法可通过将$b$的二进制分解，以分治的方式加速幂数的计算。

算法流程

1. 将幂数$b$转化为二进制数
2. 遍历二进制数中每一位，从高位到低位，若该位上的二进制数字为1，则将当前幂数乘上底数$a$，否则幂数不变。
3. 将所得的幂数对$c$取模，得到结果

实现代码

public static int powerMod(int a, int b, int c) {
    int res = 1;
    a = a % c;
    while (b > 0) {
        if ((b & 1) == 1) {
            res = (res * a) % c;
        }
        b >>= 1;
        a = (a * a) % c;
    }
    return res;
}

在代码中，a为底数，b为幂数，c为模数。首先将底数a对模数c取模，避免幂数过大导致计算过程中溢出。接下来进入循环，每次移位操作等价于将当前幂数除以2，检查其二进制位最低位。若该二进制位为1，则将结果乘上当前的底数，否则不变。随后将底数自乘，将幂数右移1位，重复上述步骤，直到幂数为0. 最后返回结果。

示例

下面通过两个示例说明快速幂算法的使用方法。

示例1

将$2^{10} \mod 5$的值计算出来。其中，$a=2,b=10,c=5$。

按照快速幂算法的步骤，将$10$转化为二进制数$1010$，从高位到低位遍历，结果为：

• 当第一位为1时，取$2$本身，此时结果为$2$
• 当第二位为0时，不变，此时结果为$2$
• 当第三位为1时，取$2^4$的值，即$16$，对$5$取模后的结果为$1$
• 当第四位为0时，不变，此时结果为$1$

最后得到$2^{10} \mod 5 = 1$

示例2

将$3^{456789} \mod 100$的值计算出来。其中，$a=3,b=456789,c=100$。

按照同样的步骤，将$456789$转化为二进制数$1110110011000110101$，从高位到低位遍历，结果为：

• 当第一位为1时，取$3$本身，此时结果为$3$
• 当第二位为0时，不变，此时结果为$3$
• 当第三位为1时，取$3^4$的值，即$81$，对$100$取模后的结果为$81$
• 当第四位为0时，不变，此时结果为$81$
• 当第五位为1时，取$3^8$的值，即$6561$，对$100$取模后的结果为$61$
• 当第六位为0时，不变，此时结果为$61$
• 当第七位为0时，不变，此时结果为$61$
• 当第八位为1时，取$3^{64}$的值，即$150094635296999121$，对$100$取模后的结果为$21$
• 当第九位为1时，取$3^{128}$的值，即$4611686018427387904$，对$100$取模后的结果为$64$
• 当第十位为1时，取$3^{256}$的值，即$1063873589237165248$，对$100$取模后的结果为$44$
• 当第十一位为0时，不变，此时结果为$44$
• 当第十二位为1时，取$3^{2048}$的值，即$3545029986111908895090048$，对$100$取模后的结果为$56$
• 当第十三位为0时，不变，此时结果为$56$
• 当第十四位为1时，取$3^{16384}$的值，即$655630285178720326763184923104$，对$100$取模后的结果为$36$
• 当第十五位为0时，不变，此时结果为$36$
• 当第十六位为1时，取$3^{131072}$的值，即$48661191875666868481...6432991824$，对$100$取模后的结果为$96$
• 当第十七位为1时，取$3^{262144}$的值，即$23626472274681353693...9890982400$，对$100$取模后的结果为$16$
• 当第十八位为0时，不变，此时结果为$16$
• 当第十九位为1时，取$3^{524288}$的值，即$669381122094400496394...664339200$，对$100$取模后的结果为$96$
• 当第二十位为1时，取$3^{1048576}$的值，即$44612008135508454900481531264...1$，对$100$取模后的结果为$36$
• 当第二十一位为0时，不变，此时结果为$36$
• 当第二十二位为1时，取$3^{2097152}$的值，即$55535850279941600865386...583003463424$，对$100$取模后的结果为$96$
• 当第二十三位为0时，不变，此时结果为$96$
• 当第二十四位为1时，取$3^{4194304}$的值，即$30880391046625326617429...489089563904$，对$100$取模后的结果为$56$
• 当第二十五位为0时，不变，此时结果为$56$
• 当第二十六位为1时，取$3^{8388608}$的值，即$89671244029286034209171382292444031916110...412652032$，对$100$取模后的结果为$16$
• 当第二十七位为0时，不变，此时结果为$16$
• 当第二十八位为1时，取$3^{16777216}$的值，即$804357544123133804235070328155150197684...465206784$，对$100$取模后的结果为$56$
• 当第二十九位为1时，取$3^{33554432}$的值，即$5757218682652774236...5507520564736000$，对$100$取模后的结果为$96$
• 当第三十位为0时，不变，此时结果为$96$
• 当第三十一位为1时，取$3^{67108864}$的值，即$324518553658426726783589...665610765209600$，对$100$取模后的结果为$16$

最后得到$3^{456789} \mod 100 = 16$

结语

快速幂算法可以有效地解决大数求幂的问题，其时间复杂度为$O(logn)$，可以有效地减少计算时间。