LeetCode 数学算法本领全解（含C++实现，持续更新）

在刷 LeetCode 的过程中，我们常常会碰到各种数学题，这类题目每每无法仅靠暴力法取胜，背后的数学原理才是通关关键。本文将详细整理 LeetCode 常见数学本领，包括理论 + 高质量 C++ 实现。

 1. 乘法逆元（Modular Multiplicative Inverse）

    应用场景

当你需要在模意义下“除以一个数”时，就要用它的 乘法逆元。
     通常用于：

• 组合数取模
  
• 模线性方程求解
  

    C++ 实现（基于费马小定理，模数必须是质数）

1. int modInverse(int a, int mod) {
2.     // 快速幂实现 a^(mod-2) % mod
3.     int res = 1;
4.     a %= mod;
5.     int b = mod - 2;
6.     while (b) {
7.         if (b & 1) res = 1LL * res * a % mod;
8.         a = 1LL * a * a % mod;
9.         b >>= 1;
10.     }
11.     return res;
12. }

复制代码

 2. 二分快速幂（Binary Exponentiation）

   应用场景

当你需要计算 a^b % mod，但 b 非常大时，用此方法可在 O(log b) 时间内完成。

1. int fastPow(int a, int b, int mod) {
2.     int res = 1;
3.     a %= mod;
4.     while (b) {
5.         if (b & 1) res = 1LL * res * a % mod;
6.         a = 1LL * a * a % mod;
7.         b >>= 1;
8.     }
9.     return res;
10. }

复制代码

3. 高斯鞋带定理（Shoelace Formula）

  应用场景

用于计算多边形面积，常见于几何类题目。

1. double polygonArea(const vector<pair<int, int>>& points) {
2.     int n = points.size();
3.     long long area = 0;
4.     for (int i = 0; i < n; i++) {
5.         int x1 = points[i].first, y1 = points[i].second;
6.         int x2 = points[(i + 1) % n].first, y2 = points[(i + 1) % n].second;
7.         area += 1LL * (x1 * y2 - x2 * y1);
8.     }
9.     return abs(area) / 2.0;
10. }

复制代码

4. 欧拉函数（Euler's Totient Function）

  应用场景

用于判断一个数 n 小于它且与它互素的整数数量。

1. int eulerTotient(int n) {
2.     int res = n;
3.     for (int i = 2; i * i <= n; i++) {
4.         if (n % i == 0) {
5.             while (n % i == 0) n /= i;
6.             res -= res / i;
7.         }
8.     }
9.     if (n > 1) res -= res / n;
10.     return res;
11. }

复制代码

5. 前缀和（Prefix Sum）

 应用场景

用于快速查询子数组和、区间统计等问题。

1. vector<int> prefixSum(const vector<int>& nums) {
2.     int n = nums.size();
3.     vector<int> prefix(n + 1);
4.     for (int i = 0; i < n; ++i) {
5.         prefix[i + 1] = prefix[i] + nums[i];
6.     }
7.     return prefix;
8. }

复制代码

6. 组合数（Combination）+ 预处置惩罚

应用场景

在模意义下计算组合数 C(n,k)C(n, k)C(n,k)，多个查询时建议预处置惩罚。

1. const int MOD = 1e9 + 7;
2. const int MAXN = 1e5 + 10;
3. int fact[MAXN], invFact[MAXN];
5. void initComb() {
6.     fact[0] = invFact[0] = 1;
7.     for (int i = 1; i < MAXN; ++i) {
8.         fact[i] = 1LL * fact[i - 1] * i % MOD;
9.     }
10.     invFact[MAXN - 1] = modInverse(fact[MAXN - 1], MOD);
11.     for (int i = MAXN - 2; i >= 1; --i) {
12.         invFact[i] = 1LL * invFact[i + 1] * (i + 1) % MOD;
13.     }
14. }
16. int comb(int n, int k) {
17.     if (k < 0 || k > n) return 0;
18.     return 1LL * fact[n] * invFact[k] % MOD * invFact[n - k] % MOD;
19. }

复制代码

7. 同余模定理（Modular Congruence）

 应用场景

用于简化模等式，快速判断两个数模相等。

1. bool isCongruent(int a, int b, int mod) {
2.     return (a - b) % mod == 0;
3. }

复制代码

8. 约数个数定理（Divisor Count）

 应用场景

用于找出一个数的全部正整数因子的数量。

1. int countDivisors(int n) {
2.     int count = 0;
3.     for (int i = 1; i * i <= n; ++i) {
4.         if (n % i == 0) {
5.             count += (i == n / i) ? 1 : 2;
6.         }
7.     }
8.     return count;
9. }

复制代码

9. 最大公约数 & 扩展欧几里得（Extended GCD）

 应用场景

办理 ax + by = gcd(a, b) 的整数解，用于求解线性同余方程。

1. int gcd(int a, int b) {
2.     return b == 0 ? a : gcd(b, a % b);
3. }
5. // 扩展欧几里得
6. int extendedGCD(int a, int b, int& x, int& y) {
7.     if (b == 0) {
8.         x = 1; y = 0;
9.         return a;
10.     }
11.     int d = extendedGCD(b, a % b, y, x);
12.     y -= a / b * x;
13.     return d;
14. }

复制代码

10. 埃拉托色尼筛法（Sieve of Eratosthenes）

 应用场景

快速生成质数列表，适用于质数计数、质因数分解。

1. vector<bool> sieve(int n) {
2.     vector<bool> isPrime(n + 1, true);
3.     isPrime[0] = isPrime[1] = false;
4.     for (int i = 2; i * i <= n; ++i) {
5.         if (isPrime[i]) {
6.             for (int j = i * i; j <= n; j += i)
7.                 isPrime[j] = false;
8.         }
9.     }
10.     return isPrime;
11. }

复制代码

11. 康托睁开（Cantor Expansion）

  应用场景

将一个排列映射为整数（排名），常用于状态压缩、唯一标识。

1. int cantor(const vector<int>& perm) {
2.     int n = perm.size();
3.     int res = 0;
4.     vector<int> used(n, 0);
5.     vector<int> fact(n, 1);
6.     for (int i = 1; i < n; ++i) fact[i] = fact[i - 1] * i;
8.     for (int i = 0; i < n; ++i) {
9.         int cnt = 0;
10.         for (int j = 0; j < perm[i]; ++j)
11.             if (!used[j]) ++cnt;
12.         res += cnt * fact[n - i - 1];
13.         used[perm[i]] = 1;
14.     }
15.     return res;
16. }

复制代码

12. 线性筛法（Linear Sieve）

  应用场景

与埃氏筛差别，线性筛可以在 O(n) 时间内获取质数和最小质因子，适合用于分解质因数等扩展操作。

1. const int MAXN = 1e6;
2. int minPrime[MAXN]; // 记录每个数的最小质因数
3. vector<int> primes;
5. void linearSieve(int n) {
6.     for (int i = 2; i <= n; ++i) {
7.         if (minPrime[i] == 0) {
8.             minPrime[i] = i;
9.             primes.push_back(i);
10.         }
11.         for (int p : primes) {
12.             if (p > minPrime[i] || i * p > n) break;
13.             minPrime[i * p] = p;
14.         }
15.     }
16. }

复制代码

13. 乘法原理（Multiplication Principle）

  应用场景

用于计数问题，如排列组合构造、密码锁、数字组合问题等。
例如：长度为 n 的数字序列，每位可以从 0~9 中任选，求方案总数。

1. int countSequences(int n) {
2.     return pow(10, n); // 10^n 个组合
3. }

复制代码

14. 排列组合递推公式

 应用场景

不使用阶乘时快速求组合数（可避免溢出），适合 n 较大时。

1. int comb(int n, int k) {
2.     long long res = 1;
3.     for (int i = 1; i <= k; ++i) {
4.         res = res * (n - i + 1) / i;
5.     }
6.     return (int)res;
7. }

复制代码

15. 数位 DP（Digit Dynamic Programming）

  应用场景

用于计数满意特定性质的整数，例如：统计不包含某些数字的数字数量、0-9 出现频率。

1. int dfs(int pos, int lead, int tight, vector<int>& digits) {
2.     // 省略具体实现，仅展示用法
3.     // 递归考虑每一位的取值可能
4.     return 0;
5. }
6. int countValid(int n) {
7.     vector<int> digits;
8.     while (n) {
9.         digits.push_back(n % 10);
10.         n /= 10;
11.     }
12.     reverse(digits.begin(), digits.end());
13.     return dfs(0, 1, 1, digits);
14. }

复制代码

16. 差分数组（Difference Array）

  应用场景

适用于频繁修改某一段区间的值，如：区间 +1 操作、区间覆盖等。

1. vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
2.     vector<int> diff(length + 1, 0);
3.     for (auto& u : updates) {
4.         int l = u[0], r = u[1], val = u[2];
5.         diff[l] += val;
6.         diff[r + 1] -= val;
7.     }
8.     for (int i = 1; i < length; ++i)
9.         diff[i] += diff[i - 1];
10.     diff.pop_back(); // 去掉多余项
11.     return diff;
12. }

复制代码

17. 矩阵快速幂（Matrix Fast Power）

  应用场景

常用于求斐波那契数列的第 n 项、线性递推式等问题，时间复杂度 O(logN)。

1. struct Matrix {
2.     long long mat[2][2];
3.     Matrix operator*(const Matrix& other) const {
4.         Matrix res{};
5.         for (int i = 0; i < 2; ++i)
6.             for (int j = 0; j < 2; ++j)
7.                 for (int k = 0; k < 2; ++k)
8.                     res.mat[i][j] += mat[i][k] * other.mat[k][j];
9.         return res;
10.     }
11. };
13. Matrix matrixPow(Matrix a, int n) {
14.     Matrix res = {{{1, 0}, {0, 1}}}; // 单位矩阵
15.     while (n) {
16.         if (n & 1) res = res * a;
17.         a = a * a;
18.         n >>= 1;
19.     }
20.     return res;
21. }

复制代码

18. 状态压缩（Bitmask Optimization）

  应用场景

适用于 n 较小（一般 n <= 20）的组合摆列问题，如旅行商问题、集合划分、状态标志

1. // 统计所有子集的和
2. int subsetSum(vector<int>& nums) {
3.     int n = nums.size(), total = 0;
4.     for (int mask = 0; mask < (1 << n); ++mask) {
5.         int sum = 0;
6.         for (int i = 0; i < n; ++i)
7.             if (mask >> i & 1)
8.                 sum += nums[i];
9.         total += sum;
10.     }
11.     return total;
12. }

复制代码

19. 中国剩余定理（Chinese Remainder Theorem, CRT）

  应用场景

求一组同余方程的最小正整数解：

1. // 求解 x ≡ a1 (mod m1), x ≡ a2 (mod m2)
2. int CRT(vector<int>& a, vector<int>& m) {
3.     int n = a.size();
4.     long long M = 1, res = 0;
5.     for (int mi : m) M *= mi;
6.     for (int i = 0; i < n; ++i) {
7.         long long Mi = M / m[i];
8.         long long ti = modInverse(Mi % m[i], m[i]);
9.         res = (res + a[i] * Mi % M * ti % M) % M;
10.     }
11.     return (int)(res % M);
12. }

复制代码

20. 最小公倍数（LCM）

  应用场景

常常用于模拟轮转、最短时间循环、周期重合类题目。

1. int lcm(int a, int b) {
2.     return a / gcd(a, b) * b;
3. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。