本文是上一篇文章《程序员必学：快速幂算法》的续集，上一篇文章详细地介绍了快速幂算法，提供了递归、非递归的2种实现方案

抛出问题

请设计一个算法求x的y次幂模z的结果：(x ^ y) % z

  • x、y、z都是整数
  • z ≠ 0, y ≥ 0
  • x、y的绝对值可能很大，比如(1234 ^ 4567) % 30

思考

由于x、y的绝对值可能很大，x ^ y的结果可能会溢出。所以先求x ^ y，再对z取模，显然是不现实的。

这里要借助模运算的一条运算规则

(a * b) % p = ((a % p) * (b % p)) % p

根据上面的推导，就可以很容易写出代码实现

递归实现

int powMod(int x, int y, int z) {
    if (y == 0) return 1 % z;
    int half = powMod(x, y >> 1, z);
    half *= half;
    if ((y & 1) == 0) { // y是偶数
        return half % z;
    } else { // y是奇数
        return (half * (x % z)) % z;
    }
}

非递归实现

int powMod(int x, int y, int z) {
    int result = 1 % z;
    x %= z;
    while (y != 0) {
        if ((y & 1) == 1) {
            result = (result * x) % z;
        }
        x = (x * x) % z;
        y >>= 1;
    }
    return result;
}

测试用例

public static void main(String[] args) {
    // 4
    System.out.println(powMod(1234, 4567, 30));
    // 699
    System.out.println(powMod2(123, 456, 789));
}

如果你特别希望我写点什么方面的内容，也可以留言建议，谢谢。欢迎关注

版权声明：本文为mjios原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/mjios/p/12703504.html