数学算法完全详解¶
重要性：⭐⭐⭐⭐ 难度：⭐⭐⭐ 学习时间：2-3天 前置知识：基础数学、位运算
📚 目录¶
数论基础¶
质数相关¶
质数判断¶
Python
def is_prime(n):
"""
判断n是否为质数
时间：O(√n)
"""
if n < 2:
return False
if n == 2:
return True
if n % 2 == 0:
return False
i = 3
while i * i <= n:
if n % i == 0:
return False
i += 2
return True
埃氏筛¶
Python
def sieve_of_eratosthenes(n):
"""
埃氏筛：找出2~n的所有质数
时间：O(n log log n)
空间：O(n)
"""
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, int(n**0.5) + 1):
if is_prime[i]:
# 标记i的所有倍数为合数
for j in range(i * i, n + 1, i):
is_prime[j] = False
return is_prime
# 测试
primes = sieve_of_eratosthenes(30)
print([i for i in range(2, 31) if primes[i]])
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
线性筛（欧拉筛）¶
Python
def linear_sieve(n):
"""
线性筛：每个合数只被最小质因子筛去
时间：O(n)
空间：O(n)
"""
is_prime = [True] * (n + 1)
primes = []
is_prime[0] = is_prime[1] = False
for i in range(2, n + 1):
if is_prime[i]:
primes.append(i)
for p in primes:
if i * p > n:
break
is_prime[i * p] = False
if i % p == 0: # p是i的最小质因子
break
return primes
# C++版本
"""
#include <bits/stdc++.h>
using namespace std;
vector<int> linearSieve(int n) {
vector<bool> isPrime(n + 1, true);
vector<int> primes;
isPrime[0] = isPrime[1] = false;
for (int i = 2; i <= n; i++) {
if (isPrime[i]) {
primes.push_back(i);
}
for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) {
isPrime[i * primes[j]] = false;
if (i % primes[j] == 0) {
break;
}
}
}
return primes;
}
"""
GCD和LCM¶
Python
def gcd(a, b):
"""
最大公约数（辗转相除法）
时间：O(log min(a, b))
"""
return a if b == 0 else gcd(b, a % b)
def lcm(a, b):
"""
最小公倍数
"""
return a // gcd(a, b) * b
# C++版本
"""
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int lcm(int a, int b) {
return a / gcd(a, b) * b;
}
"""
快速幂¶
原理¶
Text Only
计算 a^b mod m：
将b表示为二进制：b = b_k * 2^k + ... + b_1 * 2 + b_0
a^b = a^(b_k * 2^k) * ... * a^(b_1 * 2) * a^b_0
例如：a^13 = a^8 * a^4 * a^1（13 = 1101_2）
Python实现¶
Python
def fast_pow(base, exp, mod):
"""
快速幂
时间：O(log exp)
空间：O(1)
"""
result = 1
base %= mod
while exp > 0:
if exp & 1: # 如果exp是奇数
result = result * base % mod
base = base * base % mod
exp >>= 1
return result
# 测试
print(fast_pow(2, 10, 1000)) # 24
print(fast_pow(3, 100, 1000000007)) # 大数取模
C++实现（竞赛风格）¶
C++
#include <bits/stdc++.h> // 引入头文件
using namespace std;
/**
* 快速幂
* 时间：O(log exp)
* 空间：O(1)
*/
long long fastPow(long long base, long long exp, long long mod) {
long long result = 1;
base %= mod;
while (exp > 0) {
if (exp & 1) {
result = result * base % mod;
}
base = base * base % mod;
exp >>= 1;
}
return result;
}
int main() {
cout << fastPow(2, 10, 1000) << endl; // 24
cout << fastPow(3, 100, 1000000007) << endl;
return 0;
}
组合数学¶
组合数计算¶
Python
class Combination:
"""
组合数计算（预处理）
时间：预处理O(n)，查询O(1)
空间：O(n)
"""
def __init__(self, n, mod=10**9 + 7):
self.mod = mod
self.fact = [1] * (n + 1)
self.inv_fact = [1] * (n + 1)
# 阶乘
for i in range(1, n + 1):
self.fact[i] = self.fact[i - 1] * i % mod
# 逆元（费马小定理）
self.inv_fact[n] = self._pow(self.fact[n], mod - 2)
for i in range(n - 1, -1, -1):
self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % mod
def _pow(self, a, b):
"""快速幂"""
res = 1
while b > 0:
if b & 1:
res = res * a % self.mod
a = a * a % self.mod
b >>= 1
return res
def C(self, n, k):
"""组合数C(n, k)"""
if k < 0 or k > n:
return 0
return self.fact[n] * self.inv_fact[k] % self.mod * self.inv_fact[n - k] % self.mod
def P(self, n, k):
"""排列数P(n, k)"""
if k < 0 or k > n:
return 0
return self.fact[n] * self.inv_fact[n - k] % self.mod
# C++版本
"""
#include <bits/stdc++.h>
using namespace std;
class Combination {
private:
vector<long long> fact;
vector<long long> invFact;
long long mod;
long long powMod(long long a, long long b) {
long long res = 1;
a %= mod;
while (b > 0) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
public:
Combination(int n, long long m = 1e9 + 7) {
mod = m;
fact.resize(n + 1);
invFact.resize(n + 1);
fact[0] = 1;
for (int i = 1; i <= n; i++) {
fact[i] = fact[i - 1] * i % mod;
}
invFact[n] = powMod(fact[n], mod - 2);
for (int i = n - 1; i >= 0; i--) {
invFact[i] = invFact[i + 1] * (i + 1) % mod;
}
}
long long C(int n, int k) {
if (k < 0 || k > n) return 0;
return fact[n] * invFact[k] % mod * invFact[n - k] % mod;
}
long long P(int n, int k) {
if (k < 0 || k > n) return 0;
return fact[n] * invFact[n - k] % mod;
}
};
"""
卡特兰数¶
Python
def catalan(n):
"""
卡特兰数
C(n) = C(2n, n) / (n + 1)
应用场景：括号匹配、二叉树形态、出栈顺序
"""
comb = Combination(2 * n)
return comb.C(2 * n, n) * comb._pow(n + 1, comb.mod - 2) % comb.mod
位运算技巧¶
常用技巧¶
Python
# 1. 判断奇偶
is_odd = x & 1 # 1为奇数，0为偶数
# 2. 交换两个数
a ^= b
b ^= a
a ^= b
# 3. 取最低位的1
lowbit = x & (-x)
# 4. 清除最低位的1
x &= x - 1
# 5. 判断是否为2的幂
is_power_of_2 = (x & (x - 1)) == 0
# 6. 计算1的个数（汉明重量）
def count_bits(x):
count = 0
while x:
count += 1
x &= x - 1
return count
# 7. 获取第i位
bit_i = (x >> i) & 1
# 8. 设置第i位为1
x |= (1 << i)
# 9. 设置第i位为0
x &= ~(1 << i)
# 10. 切换第i位
x ^= (1 << i)
LeetCode题目详解¶
题目1：Pow(x, n)¶
题目链接：LeetCode 50
Python
class Solution:
def myPow(self, x: float, n: int) -> float:
"""
快速幂实现
时间：O(log n)
空间：O(1)
"""
if n < 0:
x = 1 / x
n = -n
result = 1
while n > 0:
if n & 1:
result *= x
x *= x
n >>= 1
return result
题目2：计数质数¶
题目链接：LeetCode 204
Python
class Solution:
def countPrimes(self, n: int) -> int:
"""
埃氏筛
时间：O(n log log n)
空间：O(n)
"""
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]:
for j in range(i * i, n, i):
is_prime[j] = False
return sum(is_prime)
题目3：超级次方¶
题目链接：LeetCode 372
Python
class Solution:
def superPow(self, a: int, b: list[int]) -> int:
"""
超级次方：计算 a^b mod 1337
其中b是一个数组，表示一个大数
利用：a^b = a^(b//10 * 10 + b%10) = (a^(b//10))^10 * a^(b%10)
"""
MOD = 1337
def pow_mod(base, exp):
"""快速幂"""
result = 1
base %= MOD
while exp > 0:
if exp & 1:
result = result * base % MOD
base = base * base % MOD
exp >>= 1
return result
result = 1
for digit in b:
# result = result^10 * a^digit
result = pow_mod(result, 10) * pow_mod(a, digit) % MOD
return result
📝 总结¶
关键要点¶
✅ 质数相关： - 埃氏筛：O(n log log n) - 线性筛：O(n)
✅ 快速幂： - 时间：O(log n) - 应用：大数幂运算、矩阵快速幂
✅ 组合数学： - 预处理阶乘和逆元 - 查询O(1)
✅ 位运算： - lowbit：x & (-x) - 清除最低位1：x & (x - 1)
下一步¶
继续学习： - 动态规划 - 更多DP技巧
📚 扩展阅读¶
- LeetCode数学专题：https://leetcode.cn/tag/math/
- CP-Algorithms：https://cp-algorithms.com/algebra/