L8 - 高阶算法与数论专题

🎯 教学目标

  1. 掌握二分答案的复杂场景应用
  2. 建立递推思维解决组合数学问题
  3. 实现高效质数筛法优化算法性能
  4. 融合多知识点解决综合性难题

🔑 核心知识点

一、二分答案升级（复杂条件验证）

典型问题：最小化最大值问题

模板代码：

1
2
3
4
5
6
7
double left=MIN, right=MAX;
for(int i=0; i<100; i++) { // 精度控制替代传统终止条件
    double mid = (left + right) / 2;
    if(check(mid)) right = mid; // check函数复杂度可突破
    else left = mid;
}
// 最终答案保留4位小数：printf("%.4f", left);

应用场景：

  • 木棍切割最大长度
  • 最小化机器人移动距离

二、递推与组合数学

1. 递推公式推导

1
2
3
4
// 斐波那契数列
f[0] = 0, f[1] = 1;
for(int i=2; i<=n; i++) 
    f[i] = f[i-1] + f[i-2];

2. 组合数递推（杨辉三角）

1
2
3
4
5
6
7
8
9
int C[10][10] = {0};
C[0][0] = 1;

for(int i=1; i<=5; i++) {
    C[i][0] = 1;
    for(int j=1; j<=i; j++)
        C[i][j] = C[i-1][j] + C[i-1][j-1]; // 递推公式
}
// C[5][2] = 10 表示5选2的组合数

经典问题：

  • 路径计数问题
  • 多项式系数计算

三、实数二分算法（精度控制艺术）

1
2
3
4
5
6
7
8
9
10
const double EPS = 1e-8; // 根据题目要求调整

double binarySearch(double left, double right) {
    while(right - left > EPS) { // 精度终止条件
        double mid = (left + right) / 2;
        if(check(mid)) right = mid;
        else left = mid;
    }
    return left;
}

典型应用：

  • 计算方程近似解
  • 几何图形交点求解

四、欧拉函数（计算互质数的个数）

定义：φ(n)表示1~n中与n互质的数的个数
​计算公式​：若n = p₁^a × p₂^b × …（p为质因子）
则 φ(n) = n × (1-1/p₁) × (1-1/p₂) × …

示例：
n = 6（质因子2,3）
φ(6) = 6 × (1-1/2) × (1-1/3) = 2
实际互质数：1,5

五、质数筛法（性能飞跃）

1. 埃拉托斯特尼筛法

1
2
3
4
5
6
7
8
9
10
11
12
// 找出100以内的所有质数
bool isPrime[101] = {0};
fill(isPrime+2, isPrime+101, true); // 初始假设2-100都是质数

for(int i=2; i<=100; i++) {
    if(isPrime[i]) {
        cout << i << " "; // 输出质数
        for(int j=i*i; j<=100; j+=i)
            isPrime[j] = false; // 标记i的倍数
    }
}
// 输出结果：2 3 5 7 11 13 ... 97

2. 欧拉线性筛法（最优时间复杂度）

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
vector<int> primes;          // 存储最终找到的所有质数
vector<bool> isPrime(n+1, true); // isPrime[i]表示i是否是质数

for (int current = 2; current <= n; current++) {
    // 当前数字如果是质数，加入质数列表
    if (isPrime[current]) {
        primes.push_back(current);
    }
    
    // 用当前数字与已有质数生成合数
    for (int prime : primes) {
        int composite = current * prime;  // 即将标记的合数
        
        // 当合数超出范围时停止标记
        if (composite > n) break;
        
        // 标记这个合数为非质数
        isPrime[composite] = false;
        
        // 核心优化逻辑：保证每个合数只被其最小质因数标记
        // 当current能被当前质数整除时，后续质数会由更大的current处理
        if (current % prime == 0) break;
    }
}

// 最终primes容器中将包含所有≤n的质数

筛法对比

算法 时间复杂度 空间复杂度 适用场景
埃氏筛 O(n log n) O(n) 普通规模数据
欧拉筛 O(n) O(n) 大规模数据

五、知识点综合应用

案例：质数间隔问题

1
2
3
4
5
6
7
8
9
10
// 找出区间[L, R]内相邻质数差的最大值
int maxGap = 0, prev = -1;
for(int i=L; i<=R; i++) {
    if(isPrime[i]) {
        if(prev != -1) 
            maxGap = max(maxGap, i - prev);
        prev = i;
    }
}
// 结合欧拉筛预处理+区间筛选优化

📝 精选练习题

题目1：质数筛法应用

描述：输入两个数a,b（10 ≤ a < b ≤ 100），输出[a,b]区间内所有质数
​样例输入​：

1
20 30

样例输出：

1
23 29

题目2：欧拉函数计算

描述：输入正整数n（n ≤ 1000），输出φ(n)的值
​样例输入​：

1
8

样例输出：

1
4  // 与8互质的数：1,3,5,7

题目3：组合数递推验证

描述：输入n和k（1 ≤ k ≤ n ≤ 10），输出C(n,k)的值
​样例输入​：

1
5 2

样例输出：

1
10

题目4：实数二分（适合学有余力）

描述：计算√a的近似值（a>1），保留3位小数
​输入​：

1
2

输出：

1
1.414

解题提示：

  • 设置二分范围left=1, right=a
  • 循环直到right-left < 1e-4
  • mid = (left+right)/2，比较mid²与a的大小

📚 学习建议

  1. 先掌握基础筛法：用埃氏筛法完成题目1
  2. 理解公式再编程：通过题目2理解欧拉函数的计算逻辑
  3. 画图辅助递推：用杨辉三角可视化题目3的递推过程
  4. 精度控制训练：题目4建议手算验证后再写代码

📝 学习路径导图