数学算法：编程中的数学魔法

当算法遇上数学，简洁而优雅

引言

在算法世界里，数学不仅仅是公式和定理，更是解决问题的强大工具。很多看似复杂的问题，只要找到背后的数学规律，往往能用寥寥几行代码优雅地解决。

本文涵盖：

  • 质数与因数分解
  • 最大公约数与最小公倍数
  • 快速幂与模运算
  • 数学规律与找规律问题
  • 组合数学基础

一、质数相关

1.1 判断质数

质数：大于1的自然数中，只能被1和自己整除的数

方法1：试除法（基础）

1
2
3
4
5
6
7
8
9
10
bool isPrime(int n) {
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;  // 排除偶数
    
    for (int i = 3; i * i <= n; i += 2) {  // 只检查奇数
        if (n % i == 0) return false;
    }
    return true;
}

优化点：

  • 只需检查到√n
  • 跳过偶数，只检查奇数

时间复杂度：O(√n)

为什么只需要检查到√n？

1
2
3
4
5
6
7
8
假设 n = a × b
如果 a 和 b 都大于√n：
  a × b > √n × √n = n（矛盾！）
  
所以必有一个因数 ≤ √n

例子：36 = 6 × 6
    如果存在因数，必有一个 ≤ 6

1.2 埃拉托斯特尼筛法（Sieve of Eratosthenes）

LeetCode 204：统计所有小于非负整数 n 的质数的数量

问题分析

1
2
3
输入：n = 10
输出：4
解释：小于10的质数有 2, 3, 5, 7

算法思路：筛法

1
2
3
4
5
6
从2开始，标记2的所有倍数为合数
从3开始，标记3的所有倍数为合数
从5开始，标记5的所有倍数为合数
...

剩下未被标记的就是质数

可视化过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
n = 20

初始：[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

标记2的倍数：
  [2, 3, ✗, 5, ✗, 7, ✗, 9, ✗, 11, ✗, 13, ✗, 15, ✗, 17, ✗, 19]
   4,6,8,10,12,14,16,18被标记

标记3的倍数：
  [2, 3, ✗, 5, ✗, 7, ✗, ✗, ✗, 11, ✗, 13, ✗, ✗, ✗, 17, ✗, 19]
   9,15也被标记

标记5的倍数：
  [2, 3, ✗, 5, ✗, 7, ✗, ✗, ✗, 11, ✗, 13, ✗, ✗, ✗, 17, ✗, 19]
   （10,15,20已经被标记过了）

质数：2, 3, 5, 7, 11, 13, 17, 19

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int countPrimes(int n) {
    if (n <= 2) return 0;
    
    vector<bool> isPrime(n, true);
    isPrime[0] = isPrime[1] = false;
    
    // 只需要从2遍历到√n
    for (int i = 2; i * i < n; ++i) {
        if (isPrime[i]) {
            // 标记i的所有倍数为合数
            // 优化：从i*i开始，因为i*(i-1)已经被更小的质数标记过了
            for (int j = i * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    // 统计质数个数
    int count = 0;
    for (int i = 2; i < n; ++i) {
        if (isPrime[i]) count++;
    }
    
    return count;
}

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

优化技巧

1
2
3
4
5
// 优化1：从i*i开始标记
for (int j = i * i; j < n; j += i)

// 优化2：跳过偶数
for (int i = 3; i * i < n; i += 2)

1.3 分解质因数

将一个正整数分解成质数的乘积

问题示例

1
2
3
4
5
输入：12
输出：2^2 × 3 = [2, 2, 3]

输入：315
输出：3^2 × 5 × 7 = [3, 3, 5, 7]

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<int> primeFactorization(int n) {
    vector<int> factors;
    
    // 处理因数2
    while (n % 2 == 0) {
        factors.push_back(2);
        n /= 2;
    }
    
    // 处理奇数因数
    for (int i = 3; i * i <= n; i += 2) {
        while (n % i == 0) {
            factors.push_back(i);
            n /= i;
        }
    }
    
    // 如果n大于1，说明n本身是质数
    if (n > 1) {
        factors.push_back(n);
    }
    
    return factors;
}

示例执行：

1
2
3
4
5
6
7
8
9
10
11
12
n = 60

处理2：60 / 2 = 30, 30 / 2 = 15
       factors = [2, 2]

处理3：15 / 3 = 5
       factors = [2, 2, 3]

处理5：5是质数，直接加入
       factors = [2, 2, 3, 5]

结果：60 = 2^2 × 3 × 5

二、最大公约数（GCD）与最小公倍数（LCM）

2.1 最大公约数（GCD）

两个或多个整数共有约数中最大的一个

欧几里得算法（辗转相除法）

数学原理：

1
2
gcd(a, b) = gcd(b, a % b)
gcd(a, 0) = a

可视化：

1
2
3
4
5
6
7
8
gcd(48, 18)
= gcd(18, 48 % 18)
= gcd(18, 12)
= gcd(12, 18 % 12)
= gcd(12, 6)
= gcd(6, 12 % 6)
= gcd(6, 0)
= 6

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 递归版本
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 迭代版本
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// C++17标准库
#include <numeric>
int result = std::gcd(a, b);

时间复杂度：O(log min(a, b))

2.2 最小公倍数（LCM）

两个或多个整数公有的倍数中最小的一个

数学关系

1
lcm(a, b) = (a × b) / gcd(a, b)

代码实现

1
2
3
4
5
6
7
8
long long lcm(int a, int b) {
    // 先除后乘，避免溢出
    return (long long)a / gcd(a, b) * b;
}

// C++17标准库
#include <numeric>
long long result = std::lcm(a, b);

注意：要防止整数溢出！

2.3 应用：简化分数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct Fraction {
    int numerator;    // 分子
    int denominator;  // 分母
    
    void simplify() {
        int g = gcd(abs(numerator), abs(denominator));
        numerator /= g;
        denominator /= g;
        
        // 确保分母为正
        if (denominator < 0) {
            numerator = -numerator;
            denominator = -denominator;
        }
    }
};

示例：

1
2
3
4
12/18 简化：
gcd(12, 18) = 6
12/6 = 2, 18/6 = 3
结果：2/3

三、快速幂与模运算

3.1 快速幂（LeetCode 50）

计算 x^n，要求时间复杂度 O(log n)

暴力方法

1
2
3
4
5
6
7
8
// O(n)
double pow(double x, int n) {
    double result = 1;
    for (int i = 0; i < n; ++i) {
        result *= x;
    }
    return result;
}

问题：n很大时太慢

快速幂（分治）

核心思想：

1
2
3
4
x^8 = (x^4)^2 = ((x^2)^2)^2

x^n = (x^(n/2))^2        (n为偶数)
x^n = x × (x^(n/2))^2     (n为奇数)

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
计算 2^10：

2^10 = (2^5)^2
2^5 = 2 × (2^2)^2
2^2 = (2^1)^2
2^1 = 2

反向计算：
2^1 = 2
2^2 = 2 × 2 = 4
2^5 = 2 × 4^2 = 2 × 16 = 32
2^10 = 32^2 = 1024

只需要4次乘法！（暴力需要9次）

代码实现（递归版）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
double myPow(double x, long long n) {
    if (n < 0) {
        x = 1 / x;
        n = -n;
    }
    return fastPow(x, n);
}

double fastPow(double x, long long n) {
    if (n == 0) return 1.0;
    
    double half = fastPow(x, n / 2);
    
    if (n % 2 == 0) {
        return half * half;
    } else {
        return half * half * x;
    }
}

代码实现（迭代版，推荐）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
double myPow(double x, long long n) {
    if (n < 0) {
        x = 1 / x;
        n = -n;
    }
    
    double result = 1.0;
    double current = x;
    
    while (n > 0) {
        if (n & 1) {  // n是奇数
            result *= current;
        }
        current *= current;  // current = x^(2^i)
        n >>= 1;
    }
    
    return result;
}

时间复杂度：O(log n)

3.2 模运算下的快速幂

LeetCode 1969：超级次方

模运算性质

1
2
(a × b) % p = ((a % p) × (b % p)) % p
(a + b) % p = ((a % p) + (b % p)) % p

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int MOD = 1e9 + 7;

long long powMod(long long x, long long n, long long mod) {
    long long result = 1;
    x %= mod;  // 先取模
    
    while (n > 0) {
        if (n & 1) {
            result = (result * x) % mod;
        }
        x = (x * x) % mod;
        n >>= 1;
    }
    
    return result;
}

应用：计算大数的幂次，防止溢出

四、数学规律问题

4.1 阶乘末尾零的个数（LeetCode 172）

给定一个整数 n，返回 n! 结果尾数中零的数量

分析

末尾的0来自于 2 × 5，因子2的数量总是比5多，所以只需要数5的个数。

示例：

1
2
3
5! = 120 → 1个0（一个5）
10! = 3628800 → 2个0（两个5：5和10）
25! → 至少6个0（5,10,15,20,25×2）

数5的个数

1
2
3
4
n / 5：有多少个5的倍数
n / 25：有多少个25的倍数（额外贡献一个5）
n / 125：有多少个125的倍数（额外贡献一个5）
...

代码实现

1
2
3
4
5
6
7
8
int trailingZeroes(int n) {
    int count = 0;
    while (n > 0) {
        n /= 5;
        count += n;
    }
    return count;
}

示例：

1
2
3
4
5
6
7
n = 25

第1轮：n = 25 / 5 = 5, count = 5
第2轮：n = 5 / 5 = 1, count = 6
第3轮：n = 1 / 5 = 0, 结束

答案：6个0

时间复杂度：O(log n)

4.2 数字1的个数（LeetCode 233）

给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的次数

问题示例

1
2
3
输入：n = 13
输出：6
解释：1, 10, 11(2个), 12, 13 → 共6个1

数位DP思路

按位统计：个位、十位、百位…各有多少个1

1
2
3
4
5
6
7
8
9
对于 n = 234，统计十位上1的个数：

当十位为1时，可能的数字：
- 010-019（百位为0）
- 110-119（百位为1）
- 210-219（百位为2）
共：3 × 10 = 30个

但234的十位是3（≠1），所以不需要特殊处理

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int countDigitOne(int n) {
    long long count = 0;
    long long factor = 1;  // 当前位的权重
    
    while (factor <= n) {
        long long higher = n / (factor * 10);  // 高位数字
        long long cur = (n / factor) % 10;     // 当前位数字
        long long lower = n % factor;          // 低位数字
        
        if (cur == 0) {
            count += higher * factor;
        } else if (cur == 1) {
            count += higher * factor + lower + 1;
        } else {
            count += (higher + 1) * factor;
        }
        
        factor *= 10;
    }
    
    return count;
}

4.3 丑数（LeetCode 264）

丑数是只包含质因数 2, 3, 5 的正整数

问题

1
2
3
输入：n = 10
输出：12
解释：1,2,3,4,5,6,8,9,10,12是前10个丑数

动态规划（三指针）

思路：

1
2
每个丑数都是之前的丑数 × 2、× 3 或 × 5 得到的
用三个指针分别维护

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int nthUglyNumber(int n) {
    vector<int> dp(n);
    dp[0] = 1;
    
    int p2 = 0, p3 = 0, p5 = 0;
    
    for (int i = 1; i < n; ++i) {
        int next2 = dp[p2] * 2;
        int next3 = dp[p3] * 3;
        int next5 = dp[p5] * 5;
        
        dp[i] = min({next2, next3, next5});
        
        // 去重
        if (dp[i] == next2) p2++;
        if (dp[i] == next3) p3++;
        if (dp[i] == next5) p5++;
    }
    
    return dp[n - 1];
}

过程演示：

1
2
3
4
5
6
7
8
9
10
初始：dp[0] = 1

i=1: next2=2, next3=3, next5=5 → dp[1]=2, p2++
i=2: next2=3, next3=3, next5=5 → dp[2]=3, p2++, p3++
i=3: next2=4, next3=6, next5=5 → dp[3]=4, p2++
i=4: next2=6, next3=6, next5=5 → dp[4]=5, p5++
i=5: next2=6, next3=6, next5=10 → dp[5]=6, p2++, p3++
...

丑数序列：1, 2, 3, 4, 5, 6, 8, 9, 10, 12...

五、组合数学

5.1 帕斯卡三角形（LeetCode 118）

杨辉三角/帕斯卡三角形

可视化

1
2
3
4
5
6
         1
       1   1
     1   2   1
   1   3   3   1
 1   4   6   4   1
1   5  10  10   5   1

规律：

1
2
每个数 = 左上方的数 + 右上方的数
C(n, k) = C(n-1, k-1) + C(n-1, k)

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<vector<int>> generate(int numRows) {
    vector<vector<int>> triangle;
    
    for (int i = 0; i < numRows; ++i) {
        vector<int> row(i + 1, 1);
        
        for (int j = 1; j < i; ++j) {
            row[j] = triangle[i-1][j-1] + triangle[i-1][j];
        }
        
        triangle.push_back(row);
    }
    
    return triangle;
}

5.2 组合数计算

计算 C(n, k) = n! / (k! × (n-k)!)

方法1：递推公式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int combination(int n, int k) {
    if (k > n) return 0;
    if (k == 0 || k == n) return 1;
    
    // C(n, k) = C(n-1, k-1) + C(n-1, k)
    vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
    
    for (int i = 0; i <= n; ++i) {
        dp[i][0] = 1;
        if (i <= k) dp[i][i] = 1;
    }
    
    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j < i && j <= k; ++j) {
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
        }
    }
    
    return dp[n][k];
}

方法2：直接计算（防溢出）

1
2
3
4
5
6
7
8
9
10
long long combination(int n, int k) {
    if (k > n - k) k = n - k;  // 利用对称性
    
    long long result = 1;
    for (int i = 0; i < k; ++i) {
        result = result * (n - i) / (i + 1);  // 边乘边除，防溢出
    }
    
    return result;
}

六、其他数学技巧

6.1 判断完全平方数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
bool isPerfectSquare(int num) {
    if (num < 0) return false;
    
    long long x = sqrt(num);
    return x * x == num;
}

// 二分查找版本
bool isPerfectSquare(int num) {
    long long left = 0, right = num;
    
    while (left <= right) {
        long long mid = left + (right - left) / 2;
        long long square = mid * mid;
        
        if (square == num) {
            return true;
        } else if (square < num) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return false;
}

6.2 整数反转（LeetCode 7）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int reverse(int x) {
    int result = 0;
    
    while (x != 0) {
        int digit = x % 10;
        x /= 10;
        
        // 检查溢出
        if (result > INT_MAX / 10 || (result == INT_MAX / 10 && digit > 7)) {
            return 0;
        }
        if (result < INT_MIN / 10 || (result == INT_MIN / 10 && digit < -8)) {
            return 0;
        }
        
        result = result * 10 + digit;
    }
    
    return result;
}

6.3 回文数（LeetCode 9）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool isPalindrome(int x) {
    // 负数和末尾为0的数（除了0本身）不是回文
    if (x < 0 || (x % 10 == 0 && x != 0)) {
        return false;
    }
    
    int reversed = 0;
    while (x > reversed) {
        reversed = reversed * 10 + x % 10;
        x /= 10;
    }
    
    // 奇数位：x == reversed / 10
    // 偶数位：x == reversed
    return x == reversed || x == reversed / 10;
}

总结

核心要点

  1. 质数判断：试除法 O(√n)，埃氏筛法 O(n log log n)
  2. GCD：欧几里得算法 O(log min(a,b))
  3. 快速幂：分治思想，O(log n)
  4. 找规律：观察数学性质，降低复杂度

常用模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// 判断质数
bool isPrime(int n) {
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

// 最大公约数
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 快速幂
long long quickPow(long long x, long long n) {
    long long result = 1;
    while (n > 0) {
        if (n & 1) result *= x;
        x *= x;
        n >>= 1;
    }
    return result;
}

// 模运算快速幂
long long powMod(long long x, long long n, long long mod) {
    long long result = 1;
    x %= mod;
    while (n > 0) {
        if (n & 1) result = (result * x) % mod;
        x = (x * x) % mod;
        n >>= 1;
    }
    return result;
}

推荐题目

入门级：

进阶级：

高级：

推荐阅读：