🔢 数学技巧 — 数论与快速幂的魔法

📖 数学技巧的核心概念

算法面试中的数学题不同于竞赛数学，主要考察几个核心知识点：素数判定与筛法、快速幂与取模、最大公约数、进制转换。掌握这些模板，大部分数学题可以套路化解。

1. 埃氏筛法

2. 快速幂

3. Python 数学工具

# 快速幂 (内置)
result = pow(base, exp, mod)  # Python 内置三参数pow

# 最大公约数
import math
math.gcd(12, 8)  # → 4

# 最小公倍数
def lcm(a, b):
    return a * b // math.gcd(a, b)

# 素数判定 (小范围)
def is_prime(n):
    if n < 2: return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0: return False
    return True

🎯 题目一：计数质数 (LC 204)

题目描述：统计所有小于非负整数 n 的质数数量。

思路分析

代码实现

class Solution:
    def countPrimes(self, n: int) -> int:
        if n <= 2:
            return 0
        is_prime = [True] * n
        is_prime[0] = is_prime[1] = False
        for i in range(2, int(n ** 0.5) + 1):
            if is_prime[i]:
                # 从 i*i 开始标记（优化）
                for j in range(i * i, n, i):
                    is_prime[j] = False
        return sum(is_prime)

复杂度分析

时间复杂度：O(n log log n)

空间复杂度：O(n)

🎯 题目二：超级次方 (LC 372)

题目描述：你的任务是计算 a^b 对 1337 取模的结果，其中 b 是一个非常大的正整数，以数组形式给出。

思路分析

代码实现

class Solution:
    def superPow(self, a: int, b: List[int]) -> int:
        MOD = 1337
        result = 1
        a %= MOD
        for digit in b:
            # result^10 * a^digit
            result = (pow(result, 10, MOD) * pow(a, digit, MOD)) % MOD
        return result

复杂度分析

时间复杂度：O(k × log 10) ≈ O(k)，k 为 b 的长度

空间复杂度：O(1)

🎯 题目三：排序数组 (LC 912)

题目描述：给你一个整数数组 nums，返回按升序排列的数组。不能使用内置排序函数。

思路分析

代码实现（归并排序）

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def merge_sort(arr):
            if len(arr) <= 1:
                return arr
            mid = len(arr) // 2
            left = merge_sort(arr[:mid])
            right = merge_sort(arr[mid:])
            return merge_two(left, right)
        
        def merge_two(left, right):
            result = []
            i = j = 0
            while i < len(left) and j < len(right):
                if left[i] <= right[j]:
                    result.append(left[i])
                    i += 1
                else:
                    result.append(right[j])
                    j += 1
            result.extend(left[i:])
            result.extend(right[j:])
            return result
        
        return merge_sort(nums)

复杂度分析

时间复杂度：O(n log n) — 每层合并 O(n)，共 log n 层

空间复杂度：O(n) — 合并时的临时数组

快速排序实现（补充）

def quick_sort(arr, lo=0, hi=None):
    if hi is None: hi = len(arr) - 1
    if lo >= hi: return
    # 随机选pivot避免最坏情况
    import random
    pivot_idx = random.randint(lo, hi)
    arr[pivot_idx], arr[hi] = arr[hi], arr[pivot_idx]
    pivot = arr[hi]
    i = lo
    for j in range(lo, hi):
        if arr[j] < pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[hi] = arr[hi], arr[i]
    quick_sort(arr, lo, i - 1)
    quick_sort(arr, i + 1, hi)

🔬 数学技巧速查表

1. 快速幂模板

def fast_pow(base, exp, mod=None):
    """快速幂: O(log exp)"""
    result = 1
    base = base % mod if mod else base
    while exp > 0:
        if exp & 1:  # 最低位为1
            result = result * base
            if mod: result %= mod
        base = base * base
        if mod: base %= mod
        exp >>= 1
    return result

2. GCD 与 LCM

import math
math.gcd(12, 8)   # 4
math.lcm(4, 6)    # 12 (Python 3.9+)

# 手写辗转相除
def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)

def lcm(a, b):
    return a // gcd(a, b) * b  # 先除后乘防爆

3. 模运算性质

# 加法取模
(a + b) % m = ((a % m) + (b % m)) % m
# 乘法取模
(a * b) % m = ((a % m) * (b % m)) % m
# 减法取模（注意负数）
(a - b) % m = ((a % m) - (b % m) + m) % m
# 幂取模 → 用快速幂
pow(a, b, m)  # Python 内置

📝 课后练习

1. LC 365 水壶问题（GCD应用）
2. LC 171 Excel表列序号（进制转换）
3. LC 50 Pow(x, n)（快速幂实现）
4. LC 1071 字符串的最大公因子（GCD+字符串）
5. LC 2183 统计可以被K整除的下标对数（数学+哈希）

🔑 本课要点回顾

• 埃氏筛：O(n log log n) 筛素数，从 i*i 开始标记
• 快速幂：O(log n) 计算大幂次，Python 用 pow(a, b, mod)
• LC 372 逐位处理：a^[d₁...dₖ] = ((a^[d₁...dₖ₋₁])^10) × a^dₖ
• 归并排序：分治+合并，O(n log n) 稳定排序
• 模运算核心性质：加法、乘法可分配取模，减法注意负数

📚 扩展阅读

• 《算法导论》第31章 数论算法
• 欧拉筛（线性筛）：O(n) 筛素数的优化
• 费马小定理与乘法逆元
• Miller-Rabin 素性测试（大数素数判定）