参考灵神在力扣上面的文档分享：分享丨模运算的世界：当加减乘除遇上取模

具体的内容可以到灵神的分享里面查看，这里只做简单的总结：

加法、乘法取模

加法： (a+b) mod m = ((a mod m) + (b mod m)) mod m

乘法： (a*b) mod m = ((a mod m) * (b mod m)) mod m

负数取模

为避免 x mod m < 0 可以写成：(x mod m + m ) mod m

除法取余

太复杂了，略过。

总结

MOD = 1_000_000_007

// 加
(a + b) % MOD

// 减
(a - b + MOD) % MOD

// 乘
a * b % MOD

// 多个数相乘，要步步取模，防止溢出
a * b % MOD * c % MOD

// 除（MOD 是质数且 b 不是 MOD 的倍数）
a * qpow(b, MOD - 2, MOD) % MOD

快速幂相关题目

50. Pow(x, n)

分治角度

$$x^2 = x^{\frac{n}{2}} * x^{\frac{n}{2}} = (x^2)^{\frac{n}{2}}$$

令 n/2 为整数，则需要分为偶数和奇数两种情况：（数学公式里面不要直接写中文，容易解析不了）

$$x^n =\begin{cases} (x^2)^{\frac{n}{2}}, n\%2 == 0 \\ x * (x^2)^{\frac{n}{2}}, n\%2 == 1 \end{cases}$$

观察发现，当 n 为奇数的时候，二分出来会多出来一项，

算法流程：

• 当 x=0.0 时，直接返回 0
• 初始化 res=1
• 当 n<0 时把问题转化成 n>=0 的情况，即执行 x= 1/x, n = -n
• 循环计算：当 n=0 是跳出，
  • 当 n%2 == 1 时，将当前 x 乘入 res，即 res *= x
  • 执行 x *= x
  • 执行 n 右移一位。

Java

class Solution {
    public double myPow(double x, int n) {
        if(x == 0.0f){
            return 0.0d;
        }
        long b = n;
        if(n < 0){
            x = 1/x;
            b = -b;
        }
        double res = 1;
        for(;b>0;b/=2){
            if(b%2 == 1){
                res *= x;
            }
            x *= x;
        }
        return res;
    }
}

Python

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x == 0.0:
            return 0.0
        if n< 0:
            x, n = 1/x, -n
        res = 1
        while n > 0:
            if n % 2 == 1:
                res *= x

            x *= x
            n >>= 1
        return res

2961. 双模幂运算

这个题主要是要写好 pow(x, n, mod)的方法

Java

class Solution {
    public List<Integer> getGoodIndices(int[][] variables, int target) {

        List<Integer> ans = new ArrayList<>();
        for(int i =0;i<variables.length;i++){
            int[] v = variables[i];
            if(pow(pow(v[0], v[1], 10), v[2], v[3]) == target){
                ans.add(i);
            }
        }
        return ans;
    }

    public long pow(long x, int n, int mod){
        long res = 1;
        long b = n;
        while(b>0){
            if(b % 2 == 1){
                res = res * x % mod;
            }
            x = x * x % mod;
            b >>= 1;
        }
        return res;
    }
}

Changelog

Last Updated: View All Changelog

• 3d2e0-

  feat(wiki): algo: 算法总结

  On 3/30/25