快速幂

LeetCode 相关题目：50. Pow(x, n)

func myPow(x float64, n int) float64 {
    res := 1.0
    if n < 0 {
        x = 1 / x
        n = -n
    }
    for n > 0 {
        if n&1 == 1 {
            res *= x
        }
        x *= x
        n >>= 1
    }
    return res
}

int 类型的位数

package math

const (
    intSize = 32 << (^uint(0) >> 63) // 32 or 64
    // 32 位系统
    // ^uint(0)：对无符号整数 0 按位取反，0xFFFFFFFF（32 个 1）
    // >> 63：右移 63 位，0xFFFFFFFF -> 0
    // 32 << 0：intSize = 32
    // 64 位系统
    // ^uint(0)：对无符号整数 0 按位取反，0xFFFFFFFFFFFFFFFF（64 个 1）
    // >> 63：右移 63 位，0xFFFFFFFFFFFFFFFF -> 1
    // 32 << 1：intSize = 64
    
    MaxInt    = 1<<(intSize-1) - 1  // MaxInt32 or MaxInt64 depending on intSize.
    MinInt    = -1 << (intSize - 1) // MinInt32 or MinInt64 depending on intSize.
)

模运算

详见 分享丨模运算的世界：当加减乘除遇上取模（模运算恒等式/费马小定理/组合数）

// 加
(a + b) % MOD

// 把任意整数 a 取模到 [0,MOD-1] 中，无论 a 是正是负
(a % MOD + MOD) % MOD

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

// 乘
a * b % MOD

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

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

取模快速幂

func modPow(x, n, mod int) int {
    res := 1
    for n > 0 {
       if n&1 == 1 {
          res = res * x % mod
       }
       x = x * x % mod
       n >>= 1
    }
    return res
}

组合数

直接通过阶乘计算会溢出，可以使用递推公式边乘边除：$C(n, i)=C(n, i-1)\times\frac{n-i+1}{i}, i\in[1, m]$

…

func comb(m, n int) int {
    // 利用对称性，减少计算量
    if m > n-m {
       m = n - m
    }
    res := 1
    for i := 1; i <= m; i++ {
       res = res * (n - i + 1) / i
    }
    return res
}

取模组合数

LeetCode 相关题目：3881. 恰好看到 K 个人的方向选择

func modComb(m, n, mod int) int {
    if m > n-m {
       m = n - m
    }
    numerator, denominator := 1, 1
    for i := 1; i <= m; i++ {
       numerator = numerator * (n - i + 1) % mod
       denominator = denominator * i % mod
    }
    return numerator * modPow(denominator, mod-2) % mod
}