# C++14 编程与数学基础讲义

本讲义旨在为学习者提供扎实的数学基础与 C++14 编程实现的结合。内容涵盖数及其运算、初等数学、初等数论、离散与组合数学以及基础编码知识，注重公式推导、性质分析、代码实现与习题巩固。

---

## 1. 数及其运算

### 1.1 自然数、整数、有理数、实数的四则运算

在计算机中，不同类型的数有着不同的存储方式与精度限制。

#### 1. 概念与性质
*   **自然数 ($\mathbb{N}$)**：$0, 1, 2, 3, \dots$。在 C++ 中常用 `unsigned int` 或 `unsigned long long` 表示。
*   **整数 ($\mathbb{Z}$)**：$\dots, -2, -1, 0, 1, 2, \dots$。C++ 中常用 `int`（通常为 32 位有符号整型）和 `long long`（通常为 64 位有符号整型）。
*   **有理数 ($\mathbb{Q}$)**：可以表示为两个整数之比 $\frac{p}{q}$（$q \neq 0$）的数。在计算机中，通常通过自定义结构体（包含分子与分母）来精确表示。
*   **实数 ($\mathbb{R}$)**：包括有理数和无理数。在 C++ 中以浮点数 `float`（单精度，约 7 位有效数字）和 `double`（双精度，约 15-17 位有效数字）来近似表示。

#### 2. C++14 精度与边界陷阱
*   **整型溢出**：有符号整型溢出在 C++ 中是**未定义行为 (Undefined Behavior)**。C++14 引入了数字分隔符（如 `1'000'000`）以增强代码可读性。
*   **浮点数精度缺失**：由于浮点数基于 IEEE 754 标准，采用二进制科学计数法存储，像 $0.1$ 这样的十进制数无法被精确转换为有限长度的二进制小数。因此，**严禁直接使用 `==` 比较两个浮点数**。

##### 浮点数安全比较方法
```cpp
#include <iostream>
#include <cmath>

// 使用 C++14 的 constexpr 与 auto 返回类型推导
constexpr double EPS = 1e-9;

auto is_equal(double a, double b) -> bool {
    return std::abs(a - b) < EPS;
}

int main() {
    double x = 0.1 + 0.2;
    double y = 0.3;
    
    if (is_equal(x, y)) {
        std::cout << "x and y are equal (within epsilon)." << std::endl;
    } else {
        std::cout << "x and y are not equal!" << std::endl;
    }
    return 0;
}
```

---

### 1.2 进制与转换：二、八、十、十六进制

#### 1. 进制转换原理
设一个 $B$ 进制数 $X$ 的表示为 $(a\_n a\_{n-1} \dots a\_1 a\_0)\_B$，其对应的十进制数值 $V$ 计算公式为：
$$V = \sum\_{i=0}^{n} a\_i \cdot B^i$$

*   **十进制转 $B$ 进制**：采用**除 $B$ 取余法**（对于整数部分）和**乘 $B$ 取整法**（对于小数部分）。
*   **$B$ 进制转十进制**：按权展开求和。

#### 2. C++14 代码实现
C++14 支持二进制字面量（以 `0b` 或 `0B` 开头）和数字分隔符 `'`。
```cpp
#include <iostream>
#include <string>
#include <algorithm>

// 将十进制整数转换为任意进制 (2 到 16)
auto decimal_to_base(long long dec, int base) -> std::string {
    if (dec == 0) return "0";
    std::string res = "";
    const char digits[] = "0123456789ABCDEF";
    bool is_negative = (dec < 0);
    if (is_negative) dec = -dec;

while (dec > 0) {
        res += digits[dec % base];
        dec /= base;
    }
    if (is_negative) res += "-";
    std::reverse(res.begin(), res.end());
    return res;
}

int main() {
    // C++14 二进制字面量与数字分隔符
    int bin_num = 0b1010'0101; 
    int hex_num = 0xA5;

std::cout << "Binary literal value: " << bin_num << std::endl; // 输出 165
    std::cout << "Hex 0xA5 value: " << hex_num << std::endl;       // 输出 165
    std::cout << "165 to Binary: " << decimal_to_base(165, 2) << std::endl;
    std::cout << "165 to Hex: " << decimal_to_base(165, 16) << std::endl;
    
    return 0;
}
```

---

## 2. 初等数学

### 2.1 初中代数：一元二次方程及其求解

#### 1. 公式推导
一元二次方程的标准形式为：
$$ax^2 + bx + c = 0 \quad (a \neq 0)$$

通过配方法推导求根公式：
1. 两边同除以 $a$：
   $$x^2 + \frac{b}{a}x + \frac{c}{a} = 0$$
2. 移项并配方：
   $$x^2 + \frac{b}{a}x + \left(\frac{b}{2a}\right)^2 = \left(\frac{b}{2a}\right)^2 - \frac{c}{a}$$
   $$\left(x + \frac{b}{2a}\right)^2 = \frac{b^2 - 4ac}{4a^2}$$
3. 记判别式 $\Delta = b^2 - 4ac$。当 $\Delta \ge 0$ 时，两边开平方：
   $$x + \frac{b}{2a} = \frac{\pm\sqrt{b^2 - 4ac}}{2a}$$
   $$x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$$

#### 2. C++14 实现（支持实根与虚根判定）
```cpp
#include <iostream>
#include <cmath>
#include <complex>
#include <utility>

// 使用 std::pair 返回一元二次方程的两个根
auto solve_quadratic(double a, double b, double c) 
    -> std::pair<std::complex<double>, std::complex<double>> {
    double delta = b * b - 4 * a * c;
    std::complex<double> x1, x2;
    if (delta >= 0) {
        x1 = (-b + std::sqrt(delta)) / (2.0 * a);
        x2 = (-b - std::sqrt(delta)) / (2.0 * a);
    } else {
        std::complex<double> sqrt_delta(0, std::sqrt(-delta));
        x1 = (-b + sqrt_delta) / (2.0 * a);
        x2 = (-b - sqrt_delta) / (2.0 * a);
    }
    return {x1, x2};
}

int main() {
    auto [r1, r2] = solve_quadratic(1, -3, 2); // 对应方程 x^2 - 3x + 2 = 0
    std::cout << "Roots of x^2 - 3x + 2 = 0: " << r1 << " and " << r2 << std::endl;
    
    auto [c1, c2] = solve_quadratic(1, 2, 5);  // 对应方程 x^2 + 2x + 5 = 0
    std::cout << "Roots of x^2 + 2x + 5 = 0: " << c1 << " and " << c2 << std::endl;
    return 0;
}
```

---

### 2.2 初中几何：基本平面几何计算

#### 1. 海伦公式 (Heron's Formula) 推导
设三角形三边长分别为 $a, b, c$，半周长 $p = \frac{a+b+c}{2}$。其面积 $S$ 为：
$$S = \sqrt{p(p-a)(p-b)(p-c)}$$

**推导思路**：
根据余弦定理：
$$\cos C = \frac{a^2 + b^2 - c^2}{2ab}$$
利用 $\sin^2 C = 1 - \cos^2 C = (1 - \cos C)(1 + \cos C)$，代入后化简展开，最终可得：
$$S = \frac{1}{2}ab \sin C = \sqrt{p(p-a)(p-b)(p-c)}$$

#### 2. C++14 三角形与圆计算实现
```cpp
#include <iostream>
#include <cmath>

constexpr double PI = 3.14159265358979323846;

// 计算两点间距离
auto distance(double x1, double y1, double x2, double y2) -> double {
    return std::hypot(x2 - x1, y2 - y1); // C++ 标准库提供的更安全的欧氏距离计算
}

// 验证三边是否能构成三角形：任意两边之和大于第三边
auto is_valid_triangle(double a, double b, double c) -> bool {
    return (a + b > c) && (a + c > b) && (b + c > a);
}

// 海伦公式计算面积
auto triangle_area(double a, double b, double c) -> double {
    if (!is_valid_triangle(a, b, c)) return 0.0;
    double p = (a + b + c) / 2.0;
    return std::sqrt(p * (p - a) * (p - b) * (p - c));
}

// 圆的面积与周长
auto circle_properties(double radius) -> std::pair<double, double> {
    double area = PI * radius * radius;
    double circumference = 2.0 * PI * radius;
    return {area, circumference};
}
```

---

## 3. 初等数论

### 3.1 基础概念与除法性质

*   **整除 ($a \mid b$)**：若存在整数 $k$ 使得 $b = k \cdot a$，则称 $a$ 整除 $b$。
*   **因数与倍数**：若 $a \mid b$，则 $a$ 是 $b$ 的因数，$b$ 是 $a$ 的倍数。
*   **指数 (Exponent)**：表示为 $a^b$，指 $a$ 连续乘以自身 $b$ 次。
*   **质数 (Prime)**：在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的数。
*   **合数 (Composite)**：在大于 1 的自然数中，除了 1 和它本身以外，还有其他因数的数（1 既不是质数也不是合数）。

---

### 3.2 向下取整、模运算、取余

在数学与计算机语言中，除法和余数的定义在处理负数时存在差异。

#### 1. 定义
*   **向下取整 ($\lfloor x \rfloor$)**：不大于 $x$ 的最大整数。
*   **取余 (Remainder)** vs **模运算 (Modulo)**：
    对于 $a$ 除以 $b$，设商为 $q$，余数为 $r$：
    $$a = q \cdot b + r$$
    *   在**取余运算**中，商 $q$ 向 0 方向截断（C++ 中的 `%` 运算符）。
    *   在**模运算**中，商 $q$ 向负无穷方向截断（数学中的 $\bmod$ 运算）。

#### 2. C++14 取模与向下取整性质
在 C++ 中，`-5 % 3` 的结果是 `-2`。如果需要数学意义上的正模数（即 $r \in [0, b-1]$），需要按如下代码进行修正：

```cpp
#include <iostream>
#include <cmath>

// 数学模运算：保证结果为非负数
auto math_mod(long long a, long long b) -> long long {
    long long r = a % b;
    return r < 0 ? r + std::abs(b) : r;
}

int main() {
    std::cout << "C++ -5 % 3 = " << (-5 % 3) << std::endl;       // 输出 -2
    std::cout << "Math -5 mod 3 = " << math_mod(-5, 3) << std::endl; // 输出 1
    
    // 向下取整 floor 与 向上取整 ceil
    std::cout << "floor(-2.3) = " << std::floor(-2.3) << std::endl; // 输出 -3
    std::cout << "ceil(-2.3) = " << std::ceil(-2.3) << std::endl;   // 输出 -2
    return 0;
}
```

---

### 3.3 算术基本定理 (唯一分解定理)

#### 1. 定理陈述与证明思路
**定理**：任何一个大于 1 的自然数 $N$，都可以唯一分解成有限个质因数的乘积：
$$N = p\_1^{a\_1} p\_2^{a\_2} \dots p\_k^{a\_k} = \prod\_{i=1}^{k} p\_i^{a\_i}$$
其中 $p\_1 < p\_2 < \dots < p\_k$ 均为质数，$a\_i$ 均为正整数。

*   **存在性证明**：用数学归纳法。对于最小的合数可以分解为两个较小数之积，而这两个较小数若非质数亦可继续分解，因因子递减，此过程必在有限步内终止于质因子。
*   **唯一性证明**：利用欧几里得引理（若质数 $p \mid ab$，则 $p \mid a$ 或 $p \mid b$）可证，若存在两种不同的分解方式，通过约去公共质因子后将导致一个质数整除另一个质数的矛盾。

#### 2. C++14 实现：单个数的质因数分解
```cpp
#include <iostream>
#include <vector>
#include <utility>

auto prime_factorize(long long n) -> std::vector<std::pair<long long, int>> {
    std::vector<std::pair<long long, int>> factors;
    for (long long i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            int count = 0;
            while (n % i == 0) {
                count++;
                n /= i;
            }
            factors.push_back({i, count});
        }
    }
    if (n > 1) {
        factors.push_back({n, 1});
    }
    return factors;
}
```

---

### 3.4 辗转相除法 (欧几里得算法)

#### 1. 原理与证明
**定理**：对于任意非负整数 $a$ 和 $b$（不全为 0），有：
$$\gcd(a, b) = \gcd(b, a \bmod b)$$

**证明**：
设 $d = \gcd(a, b)$，则 $d \mid a$ 且 $d \mid b$。
令 $r = a \bmod b$，则 $a = q \cdot b + r$（其中 $q = \lfloor a/b \rfloor$），得 $r = a - q \cdot b$。
1. 因为 $d \mid a$ 且 $d \mid b$，所以 $d \mid (a - q \cdot b)$，即 $d \mid r$。因此 $d$ 是 $b$ 和 $r$ 的公因数。
2. 设 $d'$ 是 $b$ 和 $r$ 的任意公因数，则 $d' \mid b$ 且 $d' \mid r$。
3. 同样由 $a = q \cdot b + r$ 可知，$d' \mid a$。因此 $d'$ 是 $a$ 和 $b$ 的公因数。
4. 由于 $d$ 是 $a$ 和 $b$ 的最大公因数，故 $d' \le d$。
由此可知，$a$ 和 $b$ 的最大公因数与 $b$ 和 $r$ 的最大公因数完全相同。

#### 2. C++14 实现
*注：C++17 引入了 `std::gcd`，但在 C++14 中我们需要手动实现。*

```cpp
#include <iostream>

// 尾递归版本的 gcd
auto gcd(long long a, long long b) -> long long {
    return b == 0 ? a : gcd(b, a % b);
}

// 迭代版本的 gcd（效率更高，避免栈溢出）
auto gcd_iter(long long a, long long b) -> long long {
    while (b != 0) {
        long long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// 最小公倍数 (LCM)
auto lcm(long long a, long long b) -> long long {
    if (a == 0 || b == 0) return 0;
    return (a / gcd_iter(a, b)) * b; // 先除后乘防止溢出
}
```

---

### 3.5 素数筛法

#### 1. 埃拉托斯特尼筛法 (Sieve of Eratosthenes)
*   **原理**：从 2 开始，将每个质数的倍数（从自身平方开始）标记为合数。
*   **时间复杂度**：$O(N \log \log N)$。
*   **缺点**：同一个合数会被多个质因子重复标记（例如 12 既被 2 标记，也被 3 标记）。

#### 2. 线性筛法 / 欧拉筛法 (Sieve of Euler)
*   **原理**：保证每个合数**只被其最小的质因数**筛选一次。
*   **性质证明**：
    在代码中，有一步关键控制：`if (i % primes[j] == 0) break;`
    设当前数 $i$ 的最小质因数为 $p\_1$（即 $primes[j] = p\_1$）。
    那么对于任何 $p\_k > p\_1$，数 $M = i \times p\_k$ 的最小质因数应当是 $p\_1$ 而非 $p\_k$。如果我们不在此处 break，继续用 $p\_k$ 去筛 $M$，这就违背了“每个数只被其最小质因子筛去”的原则。因此，一旦发现 $i$ 能被当前质数整除，必须立即退出，留待以后由更小的质因子去筛掉它。
*   **时间复杂度**：$O(N)$。

#### 3. C++14 两种筛法代码对比
```cpp
#include <iostream>
#include <vector>

// 埃氏筛法
auto eratosthenes(int n) -> std::vector<bool> {
    std::vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= n; ++i) {
        if (is_prime[i]) {
            for (int j = i * i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }
    return is_prime;
}

// 线性筛法 (欧拉筛)
auto euler_sieve(int n) -> std::pair<std::vector<int>, std::vector<bool>> {
    std::vector<bool> is_prime(n + 1, true);
    std::vector<int> primes;
    is_prime[0] = is_prime[1] = false;

for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
        }
        for (size_t j = 0; j < primes.size() && i * primes[j] <= n; ++j) {
            is_prime[i * primes[j]] = false;
            if (i % primes[j] == 0) {
                break; // 保证线性复杂度的关键所在
            }
        }
    }
    return {primes, is_prime};
}
```

---

## 4. 离散与组合数学

### 4.1 集合 (Sets)

#### 1. 概念与运算
*   **交集 ($\cap$)**：$A \cap B = \{x \mid x \in A \text{ 且 } x \in B\}$
*   **并集 ($\cup$)**：$A \cup B = \{x \mid x \in A \text{ 或 } x \in B\}$
*   **差集 ($\setminus$)**：$A \setminus B = \{x \mid x \in A \text{ 且 } x \notin B\}$

#### 2. C++14 标准库操作
C++ 标准库在 `<algorithm>` 中提供了高效的有序集合操作函数，要求输入区间必须是有序的。

```cpp
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

int main() {
    std::vector<int> setA = {1, 3, 5, 7, 9};
    std::vector<int> setB = {3, 4, 5, 6, 7};
    
    // 准备容器存储结果
    std::vector<int> intersect_res;
    std::vector<int> union_res;
    
    // 1. 求交集
    std::set_intersection(setA.begin(), setA.end(),
                          setB.begin(), setB.end(),
                          std::back_inserter(intersect_res));
                          
    // 2. 求并集
    std::set_union(setA.begin(), setA.end(),
                    setB.begin(), setB.end(),
                    std::back_inserter(union_res));
                    
    // 使用 C++11/14 范围 for 循环输出
    std::cout << "Intersection: ";
    for (auto x : intersect_res) std::cout << x << " ";
    std::cout << "\nUnion: ";
    for (auto x : union_res) std::cout << x << " ";
    std::cout << std::endl;
    
    return 0;
}
```

---

### 4.2 加法原理与乘法原理

*   **加法原理（分类计数）**：若完成一件事有 $n$ 类方法，第 $i$ 类方法中有 $m\_i$ 种不同的方法，则完成这件事共有：
    $$N = m\_1 + m\_2 + \dots + m\_n$$
*   **乘法原理（分步计数）**：若完成一件事需要 $n$ 个步骤，第 $i$ 步有 $m\_i$ 种不同的方法，则完成这件事共有：
    $$N = m\_1 \times m\_2 \times \dots \times m\_n$$

---

### 4.3 排列与组合

#### 1. 公式与推导
*   **排列数 $P(n, k)$**（或表示为 $A\_n^k$）：从 $n$ 个不同元素中取出 $k$ 个元素排成一列。
    $$P(n, k) = n \times (n-1) \times \dots \times (n-k+1) = \frac{n!}{(n-k)!}$$
*   **组合数 $C(n, k)$**（或表示为 $\binom{n}{k}$）：从 $n$ 个不同元素中取出 $k$ 个元素组成一组，不考虑顺序。
    因为从 $k$ 个元素的组合中，可以产生 $k!$ 种不同的排列，所以：
    $$C(n, k) = \frac{P(n, k)}{k!} = \frac{n!}{k!(n-k)!}$$

#### 2. 递推性质（杨辉三角的核心性质）
$$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$
*   **证明（组合意义）**：从 $n$ 个元素中选 $k$ 个，我们关注其中一个特定的元素 $x$。
    *   若**选中 $x$**，则需从剩余的 $n-1$ 个元素中选 $k-1$ 个，方案数为 $\binom{n-1}{k-1}$。
    *   若**不选 $x$**，则需从剩余的 $n-1$ 个元素中选 $k$ 个，方案数为 $\binom{n-1}{k}$。
    *   根据加法原理，总方案数即为两部分之和。

#### 3. C++14 实现（避免大数溢出的动态规划写法）
直接计算阶乘容易引发数值溢出。使用递推式或动态规划可以在计算中避免乘法产生的中途溢出。

```cpp
#include <iostream>
#include <vector>

// 利用递推公式计算组合数 C(n, k)
auto select_combin(int n, int k) -> long long {
    if (k < 0 || k > n) return 0;
    if (k == 0 || k == n) return 1;
    if (k > n / 2) k = n - k; // 优化空间：利用对称性 C(n, k) == C(n, n-k)

std::vector<long long> dp(k + 1, 0);
    dp[0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = std::min(i, k); j > 0; --j) {
            dp[j] = dp[j] + dp[j - 1];
        }
    }
    return dp[k];
}
```

---

### 4.4 杨辉三角 (Pascal's Triangle)

杨辉三角（或帕斯卡三角形）与二项式定理的展开系数紧密关联：
$$(a+b)^n = \sum\_{k=0}^{n} \binom{n}{k} a^{n-k}b^k$$

#### 1. C++14 打印杨辉三角
```cpp
#include <iostream>
#include <vector>
#include <iomanip>

auto print_pascal_triangle(int rows) -> void {
    std::vector<std::vector<long long>> triangle(rows);
    for (int i = 0; i < rows; ++i) {
        triangle[i].resize(i + 1, 1);
        for (int j = 1; j < i; ++j) {
            triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
        }
    }

// 格式化输出
    for (int i = 0; i < rows; ++i) {
        std::cout << std::string((rows - i) * 2, ' '); // 打印前置空格保持居中
        for (int j = 0; j <= i; ++j) {
            std::cout << std::setw(4) << triangle[i][j];
        }
        std::cout << std::endl;
    }
}

int main() {
    print_pascal_triangle(6);
    return 0;
}
```

---

## 5. 其他

### 5.1 ASCII 码

#### 1. 核心映射区间
ASCII (American Standard Code for Information Interchange) 使用 7 位二进制数来表示 128 个字符。
*   **数字字符 `'0'` - `'9'`**：ASCII 范围 $48 \sim 57$ (十六进制 $0x30 \sim 0x39$)
*   **大写字母 `'A'` - `'Z'`**：ASCII 范围 $65 \sim 90$ (十六进制 $0x41 \sim 0x5A$)
*   **小写字母 `'a'` - `'z'`**：ASCII 范围 $97 \sim 122$ (十六进制 $0x61 \sim 0x7A$)

#### 2. 位运算与高效转换
大写与小写字母在 ASCII 码上正好相差 32（即二进制下的 $2^5$，对应字符 `' '` 的 ASCII 码）。
*   **大小写转换**：可以通过与 $32$ 进行异或（`^`）来实现快速转换。
*   **字符转数字**：直接通过减去字符 `'0'` 来获得其整数值。

```cpp
#include <iostream>

int main() {
    char lower = 'g';
    // 1. 小写转大写：利用位运算异或 32 (0x20)
    char upper = lower ^ 32; 
    std::cout << lower << " -> " << upper << std::endl; // 输出 g -> G
    
    // 2. 利用位运算与 223 (0xDF) 也可以将字符强制转大写
    char some_char = 'k';
    std::cout << static_cast<char>(some_char & 0xDF) << std::endl; // 输出 K

// 3. 字符数字转数值
    char num_char = '7';
    int num_val = num_char - '0';
    std::cout << "Char '7' to int: " << num_val << std::endl; // 输出 7
    
    return 0;
}
```

---

## 6. 综合练习题与解析

### 练习题 1：进制转换与回文判定
**题目描述**：
编写一个 C++14 函数，接收一个十进制正整数 $N$，将其转换为 $B$ 进制数（$2 \le B \le 16$），并判断该 $B$ 进制下的字符串表示是否为“回文串”（正读和反读都相同的字符串）。

#### C++14 实现与解析
```cpp
#include <iostream>
#include <string>
#include <algorithm>

// 辅助函数：十进制转 B 进制
auto to_base(long long n, int b) -> std::string {
    const char table[] = "0123456789ABCDEF";
    std::string s = "";
    while (n > 0) {
        s += table[n % b];
        n /= b;
    }
    std::reverse(s.begin(), s.end());
    return s.empty() ? "0" : s;
}

// 判定回文
auto is_palindrome(const std::string& s) -> bool {
    int left = 0;
    int right = s.length() - 1;
    while (left < right) {
        if (s[left] != s[right]) return false;
        left++;
        right--;
    }
    return true;
}

int main() {
    long long n = 121;
    int base = 10;
    std::string representation = to_base(n, base);
    
    std::cout << "Number " << n << " in base " << base << " is: " << representation << std::endl;
    if (is_palindrome(representation)) {
        std::cout << "It is a palindrome!" << std::endl;
    } else {
        std::cout << "It is not a palindrome." << std::endl;
    }
    return 0;
}
```
**解析**：
本题将进制转换与双指针字符串遍历技术相结合。在 `to_base` 中，通过不断对基数 $B$ 取余，自底向上构建目标字符串。由于最低位先出，构建完毕后需利用 `std::reverse` 反转。随后在 `is_palindrome` 中，使用左右指针从两端向中间汇聚，时间复杂度为 $O(\log\_B N)$。

---

### 练习题 2：线性筛法求区间质数和
**题目描述**：
输入一个整数 $M$，计算并输出 $[1, M]$ 区间内所有质数的累加和。由于数据范围可能较大，要求算法在 $O(M)$ 线性时间内完成。

#### C++14 实现与解析
```cpp
#include <iostream>
#include <vector>
#include <numeric>

auto get_prime_sum(int m) -> long long {
    if (m < 2) return 0;
    std::vector<bool> is_prime(m + 1, true);
    std::vector<int> primes;
    is_prime[0] = is_prime[1] = false;
    
    long long sum = 0;
    for (int i = 2; i <= m; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
            sum += i; // 累加当前发现的质数
        }
        for (size_t j = 0; j < primes.size() && i * primes[j] <= m; ++j) {
            is_prime[i * primes[j]] = false;
            if (i % primes[j] == 0) {
                break; // 保证每个合数只被其最小质因数标记
            }
        }
    }
    return sum;
}

int main() {
    int m = 100'000; // 使用 C++14 数字分隔符
    std::cout << "Sum of primes up to " << m << " is " << get_prime_sum(m) << std::endl;
    return 0;
}
```
**解析**：
相较于普通筛法的 $O(M \log \log M)$，线性筛通过 `i % primes[j] == 0` 这一关键逻辑控制，让每个合数都仅被其最小质因数标记。例如在遇到 4 之前，当 $i=2$，我们将 $2 \times 2 = 4$ 标为合数。当 $i=4$，由于 $4 \bmod 2 == 0$，程序会在筛选 $4 \times 3 = 12$ 前中断，从而避免了 $12$ 被重复筛选（$12$ 留到 $i=6$ 时被 $6 \times 2 = 12$ 所筛选）。这确保了整体时间复杂度严格在 $O(M)$ 内完成。

---

### 练习题 3：不相邻选球问题（组合数学应用）
**题目描述**：
在一排 $N$ 个位置的网格中放入 $K$ 个完全相同的球（每个位置最多放一个球），要求任意两个球不能相邻，求有多少种摆放方案？

#### 数学推导与证明
设方案数为 $S$。我们可以把放球后的状态抽象成“放了球的网格”与“未放球的网格”。
1. 首先，未放球的网格共有 $N - K$ 个。
2. 将这 $N - K$ 个未放球的网格排成一排。它们之间以及两端会形成一系列“空隙”，空隙的个数为 $(N - K) + 1$。
3. 如果我们将这 $K$ 个球塞入这些空隙中，由于每个空隙最多只能塞入一个球，这能确保任意两球绝不相邻。
4. 因此，问题等价于从这 $N - K + 1$ 个空隙中选择 $K$ 个位置放球：
   $$S = \binom{N - K + 1}{K}$$

#### C++14 实现与解析
```cpp
#include <iostream>
#include <vector>

// 利用前面设计的动态规划 C(n, k) 求解
auto solve_non_adjacent(int n, int k) -> long long {
    if (k > (n + 1) / 2) return 0; // 鸽巢原理，若球数过多则必定有相邻
    return select_combin(n - k + 1, k);
}

int main() {
    int N = 10;
    int K = 4;
    std::cout << "Number of ways to place " << K << " balls in " << N 
              << " slots without being adjacent: " << solve_non_adjacent(N, K) << std::endl;
    return 0;
}
```
**解析**：
该经典物理背景问题通过“插空法”将带有不相邻限制的计数转换成了常规无限制的组合数。在代码实现中，首先进行了边界剪枝：当 $K > \lfloor(N+1)/2\rfloor$ 时，由鸽巢原理可知，必定会有两球相邻，故直接返回 0。随后调用防溢出的 `select_combin` 进行高效求值。

C++14 编程与数学基础讲义

1. 数及其运算

1.1 自然数、整数、有理数、实数的四则运算

在计算机中，不同类型的数有着不同的存储方式与精度限制。

1. 概念与性质

自然数 ($\mathbb{N}$)：$0, 1, 2, 3, \dots$。在 C++ 中常用 unsigned int 或 unsigned long long 表示。
整数 ($\mathbb{Z}$)：$\dots, -2, -1, 0, 1, 2, \dots$。C++ 中常用 int（通常为 32 位有符号整型）和 long long（通常为 64 位有符号整型）。
有理数 ($\mathbb{Q}$)：可以表示为两个整数之比 $\frac{p}{q}$（$q \neq 0$）的数。在计算机中，通常通过自定义结构体（包含分子与分母）来精确表示。
实数 ($\mathbb{R}$)：包括有理数和无理数。在 C++ 中以浮点数 float（单精度，约 7 位有效数字）和 double（双精度，约 15-17 位有效数字）来近似表示。

2. C++14 精度与边界陷阱

整型溢出：有符号整型溢出在 C++ 中是未定义行为 (Undefined Behavior)。C++14 引入了数字分隔符（如 1'000'000）以增强代码可读性。
浮点数精度缺失：由于浮点数基于 IEEE 754 标准，采用二进制科学计数法存储，像 $0.1$ 这样的十进制数无法被精确转换为有限长度的二进制小数。因此，严禁直接使用 == 比较两个浮点数。

浮点数安全比较方法

#include <iostream>
#include <cmath>

// 使用 C++14 的 constexpr 与 auto 返回类型推导
constexpr double EPS = 1e-9;

auto is_equal(double a, double b) -> bool {
    return std::abs(a - b) < EPS;
}

int main() {
    double x = 0.1 + 0.2;
    double y = 0.3;

    if (is_equal(x, y)) {
        std::cout << "x and y are equal (within epsilon)." << std::endl;
    } else {
        std::cout << "x and y are not equal!" << std::endl;
    }
    return 0;
}

1.2 进制与转换：二、八、十、十六进制

1. 进制转换原理

设一个 $B$ 进制数 $X$ 的表示为 $(a_n a_{n-1} \dots a_1 a_0)_B$，其对应的十进制数值 $V$ 计算公式为： $$V = \sum_{i=0}^{n} a_i \cdot B^i$$

十进制转 $B$ 进制：采用除 $B$ 取余法（对于整数部分）和乘 $B$ 取整法（对于小数部分）。
$B$ 进制转十进制：按权展开求和。

2. C++14 代码实现

C++14 支持二进制字面量（以 0b 或 0B 开头）和数字分隔符 '。

#include <iostream>
#include <string>
#include <algorithm>

// 将十进制整数转换为任意进制 (2 到 16)
auto decimal_to_base(long long dec, int base) -> std::string {
    if (dec == 0) return "0";
    std::string res = "";
    const char digits[] = "0123456789ABCDEF";
    bool is_negative = (dec < 0);
    if (is_negative) dec = -dec;

    while (dec > 0) {
        res += digits[dec % base];
        dec /= base;
    }
    if (is_negative) res += "-";
    std::reverse(res.begin(), res.end());
    return res;
}

int main() {
    // C++14 二进制字面量与数字分隔符
    int bin_num = 0b1010'0101; 
    int hex_num = 0xA5;

    std::cout << "Binary literal value: " << bin_num << std::endl; // 输出 165
    std::cout << "Hex 0xA5 value: " << hex_num << std::endl;       // 输出 165
    std::cout << "165 to Binary: " << decimal_to_base(165, 2) << std::endl;
    std::cout << "165 to Hex: " << decimal_to_base(165, 16) << std::endl;

    return 0;
}

2. 初等数学

2.1 初中代数：一元二次方程及其求解

1. 公式推导

一元二次方程的标准形式为： $$ax^2 + bx + c = 0 \quad (a \neq 0)$$

通过配方法推导求根公式： 1. 两边同除以 $a$： $$x^2 + \frac{b}{a}x + \frac{c}{a} = 0$$ 2. 移项并配方： $$x^2 + \frac{b}{a}x + \left(\frac{b}{2a}\right)^2 = \left(\frac{b}{2a}\right)^2 - \frac{c}{a}$$ $$\left(x + \frac{b}{2a}\right)^2 = \frac{b^2 - 4ac}{4a^2}$$ 3. 记判别式 $\Delta = b^2 - 4ac$。当 $\Delta \ge 0$ 时，两边开平方： $$x + \frac{b}{2a} = \frac{\pm\sqrt{b^2 - 4ac}}{2a}$$ $$x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$$

2. C++14 实现（支持实根与虚根判定）

#include <iostream>
#include <cmath>
#include <complex>
#include <utility>

// 使用 std::pair 返回一元二次方程的两个根
auto solve_quadratic(double a, double b, double c) 
    -> std::pair<std::complex<double>, std::complex<double>> {
    double delta = b * b - 4 * a * c;
    std::complex<double> x1, x2;
    if (delta >= 0) {
        x1 = (-b + std::sqrt(delta)) / (2.0 * a);
        x2 = (-b - std::sqrt(delta)) / (2.0 * a);
    } else {
        std::complex<double> sqrt_delta(0, std::sqrt(-delta));
        x1 = (-b + sqrt_delta) / (2.0 * a);
        x2 = (-b - sqrt_delta) / (2.0 * a);
    }
    return {x1, x2};
}

int main() {
    auto [r1, r2] = solve_quadratic(1, -3, 2); // 对应方程 x^2 - 3x + 2 = 0
    std::cout << "Roots of x^2 - 3x + 2 = 0: " << r1 << " and " << r2 << std::endl;

    auto [c1, c2] = solve_quadratic(1, 2, 5);  // 对应方程 x^2 + 2x + 5 = 0
    std::cout << "Roots of x^2 + 2x + 5 = 0: " << c1 << " and " << c2 << std::endl;
    return 0;
}

2.2 初中几何：基本平面几何计算

1. 海伦公式 (Heron's Formula) 推导

设三角形三边长分别为 $a, b, c$，半周长 $p = \frac{a+b+c}{2}$。其面积 $S$ 为： $$S = \sqrt{p(p-a)(p-b)(p-c)}$$

推导思路：根据余弦定理： $$\cos C = \frac{a^2 + b^2 - c^2}{2ab}$$ 利用 $\sin^2 C = 1 - \cos^2 C = (1 - \cos C)(1 + \cos C)$，代入后化简展开，最终可得： $$S = \frac{1}{2}ab \sin C = \sqrt{p(p-a)(p-b)(p-c)}$$

2. C++14 三角形与圆计算实现

#include <iostream>
#include <cmath>

constexpr double PI = 3.14159265358979323846;

// 计算两点间距离
auto distance(double x1, double y1, double x2, double y2) -> double {
    return std::hypot(x2 - x1, y2 - y1); // C++ 标准库提供的更安全的欧氏距离计算
}

// 验证三边是否能构成三角形：任意两边之和大于第三边
auto is_valid_triangle(double a, double b, double c) -> bool {
    return (a + b > c) && (a + c > b) && (b + c > a);
}

// 海伦公式计算面积
auto triangle_area(double a, double b, double c) -> double {
    if (!is_valid_triangle(a, b, c)) return 0.0;
    double p = (a + b + c) / 2.0;
    return std::sqrt(p * (p - a) * (p - b) * (p - c));
}

// 圆的面积与周长
auto circle_properties(double radius) -> std::pair<double, double> {
    double area = PI * radius * radius;
    double circumference = 2.0 * PI * radius;
    return {area, circumference};
}

3. 初等数论

3.1 基础概念与除法性质

整除 ($a \mid b$)：若存在整数 $k$ 使得 $b = k \cdot a$，则称 $a$ 整除 $b$。
因数与倍数：若 $a \mid b$，则 $a$ 是 $b$ 的因数，$b$ 是 $a$ 的倍数。
指数 (Exponent)：表示为 $a^b$，指 $a$ 连续乘以自身 $b$ 次。
质数 (Prime)：在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的数。
合数 (Composite)：在大于 1 的自然数中，除了 1 和它本身以外，还有其他因数的数（1 既不是质数也不是合数）。

3.2 向下取整、模运算、取余

在数学与计算机语言中，除法和余数的定义在处理负数时存在差异。

1. 定义

向下取整 ($\lfloor x \rfloor$)：不大于 $x$ 的最大整数。
取余 (Remainder) vs 模运算 (Modulo)：对于 $a$ 除以 $b$，设商为 $q$，余数为 $r$： $$a = q \cdot b + r$$
- 在取余运算中，商 $q$ 向 0 方向截断（C++ 中的 % 运算符）。
- 在模运算中，商 $q$ 向负无穷方向截断（数学中的 $\bmod$ 运算）。

2. C++14 取模与向下取整性质

在 C++ 中，-5 % 3 的结果是 -2。如果需要数学意义上的正模数（即 $r \in [0, b-1]$），需要按如下代码进行修正：

#include <iostream>
#include <cmath>

// 数学模运算：保证结果为非负数
auto math_mod(long long a, long long b) -> long long {
    long long r = a % b;
    return r < 0 ? r + std::abs(b) : r;
}

int main() {
    std::cout << "C++ -5 % 3 = " << (-5 % 3) << std::endl;       // 输出 -2
    std::cout << "Math -5 mod 3 = " << math_mod(-5, 3) << std::endl; // 输出 1

    // 向下取整 floor 与 向上取整 ceil
    std::cout << "floor(-2.3) = " << std::floor(-2.3) << std::endl; // 输出 -3
    std::cout << "ceil(-2.3) = " << std::ceil(-2.3) << std::endl;   // 输出 -2
    return 0;
}

3.3 算术基本定理 (唯一分解定理)

1. 定理陈述与证明思路

定理：任何一个大于 1 的自然数 $N$，都可以唯一分解成有限个质因数的乘积： $$N = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k} = \prod_{i=1}^{k} p_i^{a_i}$$ 其中 $p_1 < p_2 < \dots < p_k$ 均为质数，$a_i$ 均为正整数。

存在性证明：用数学归纳法。对于最小的合数可以分解为两个较小数之积，而这两个较小数若非质数亦可继续分解，因因子递减，此过程必在有限步内终止于质因子。
唯一性证明：利用欧几里得引理（若质数 $p \mid ab$，则 $p \mid a$ 或 $p \mid b$）可证，若存在两种不同的分解方式，通过约去公共质因子后将导致一个质数整除另一个质数的矛盾。

2. C++14 实现：单个数的质因数分解

#include <iostream>
#include <vector>
#include <utility>

auto prime_factorize(long long n) -> std::vector<std::pair<long long, int>> {
    std::vector<std::pair<long long, int>> factors;
    for (long long i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            int count = 0;
            while (n % i == 0) {
                count++;
                n /= i;
            }
            factors.push_back({i, count});
        }
    }
    if (n > 1) {
        factors.push_back({n, 1});
    }
    return factors;
}

3.4 辗转相除法 (欧几里得算法)

1. 原理与证明

定理：对于任意非负整数 $a$ 和 $b$（不全为 0），有： $$\gcd(a, b) = \gcd(b, a \bmod b)$$

证明：设 $d = \gcd(a, b)$，则 $d \mid a$ 且 $d \mid b$。令 $r = a \bmod b$，则 $a = q \cdot b + r$（其中 $q = \lfloor a/b \rfloor$），得 $r = a - q \cdot b$。 1. 因为 $d \mid a$ 且 $d \mid b$，所以 $d \mid (a - q \cdot b)$，即 $d \mid r$。因此 $d$ 是 $b$ 和 $r$ 的公因数。 2. 设 $d'$ 是 $b$ 和 $r$ 的任意公因数，则 $d' \mid b$ 且 $d' \mid r$。 3. 同样由 $a = q \cdot b + r$ 可知，$d' \mid a$。因此 $d'$ 是 $a$ 和 $b$ 的公因数。 4. 由于 $d$ 是 $a$ 和 $b$ 的最大公因数，故 $d' \le d$。由此可知，$a$ 和 $b$ 的最大公因数与 $b$ 和 $r$ 的最大公因数完全相同。

2. C++14 实现

注：C++17 引入了 std::gcd，但在 C++14 中我们需要手动实现。

#include <iostream>

// 尾递归版本的 gcd
auto gcd(long long a, long long b) -> long long {
    return b == 0 ? a : gcd(b, a % b);
}

// 迭代版本的 gcd（效率更高，避免栈溢出）
auto gcd_iter(long long a, long long b) -> long long {
    while (b != 0) {
        long long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// 最小公倍数 (LCM)
auto lcm(long long a, long long b) -> long long {
    if (a == 0 || b == 0) return 0;
    return (a / gcd_iter(a, b)) * b; // 先除后乘防止溢出
}

3.5 素数筛法

1. 埃拉托斯特尼筛法 (Sieve of Eratosthenes)

原理：从 2 开始，将每个质数的倍数（从自身平方开始）标记为合数。
时间复杂度：$O(N \log \log N)$。
缺点：同一个合数会被多个质因子重复标记（例如 12 既被 2 标记，也被 3 标记）。

2. 线性筛法 / 欧拉筛法 (Sieve of Euler)

原理：保证每个合数只被其最小的质因数筛选一次。
性质证明：在代码中，有一步关键控制：if (i % primes[j] == 0) break; 设当前数 $i$ 的最小质因数为 $p_1$（即 $primes[j] = p_1$）。那么对于任何 $p_k > p_1$，数 $M = i \times p_k$ 的最小质因数应当是 $p_1$ 而非 $p_k$。如果我们不在此处 break，继续用 $p_k$ 去筛 $M$，这就违背了“每个数只被其最小质因子筛去”的原则。因此，一旦发现 $i$ 能被当前质数整除，必须立即退出，留待以后由更小的质因子去筛掉它。
时间复杂度：$O(N)$。

3. C++14 两种筛法代码对比

#include <iostream>
#include <vector>

// 埃氏筛法
auto eratosthenes(int n) -> std::vector<bool> {
    std::vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= n; ++i) {
        if (is_prime[i]) {
            for (int j = i * i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }
    return is_prime;
}

// 线性筛法 (欧拉筛)
auto euler_sieve(int n) -> std::pair<std::vector<int>, std::vector<bool>> {
    std::vector<bool> is_prime(n + 1, true);
    std::vector<int> primes;
    is_prime[0] = is_prime[1] = false;

    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
        }
        for (size_t j = 0; j < primes.size() && i * primes[j] <= n; ++j) {
            is_prime[i * primes[j]] = false;
            if (i % primes[j] == 0) {
                break; // 保证线性复杂度的关键所在
            }
        }
    }
    return {primes, is_prime};
}

4. 离散与组合数学

4.1 集合 (Sets)

1. 概念与运算

交集 ($\cap$)：$A \cap B = {x \mid x \in A \text{ 且 } x \in B}$
并集 ($\cup$)：$A \cup B = {x \mid x \in A \text{ 或 } x \in B}$
差集 ($\setminus$)：$A \setminus B = {x \mid x \in A \text{ 且 } x \notin B}$

2. C++14 标准库操作

C++ 标准库在 <algorithm> 中提供了高效的有序集合操作函数，要求输入区间必须是有序的。

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

int main() {
    std::vector<int> setA = {1, 3, 5, 7, 9};
    std::vector<int> setB = {3, 4, 5, 6, 7};

    // 准备容器存储结果
    std::vector<int> intersect_res;
    std::vector<int> union_res;

    // 1. 求交集
    std::set_intersection(setA.begin(), setA.end(),
                          setB.begin(), setB.end(),
                          std::back_inserter(intersect_res));

    // 2. 求并集
    std::set_union(setA.begin(), setA.end(),
                    setB.begin(), setB.end(),
                    std::back_inserter(union_res));

    // 使用 C++11/14 范围 for 循环输出
    std::cout << "Intersection: ";
    for (auto x : intersect_res) std::cout << x << " ";
    std::cout << "\nUnion: ";
    for (auto x : union_res) std::cout << x << " ";
    std::cout << std::endl;

    return 0;
}

4.2 加法原理与乘法原理

加法原理（分类计数）：若完成一件事有 $n$ 类方法，第 $i$ 类方法中有 $m_i$ 种不同的方法，则完成这件事共有： $$N = m_1 + m_2 + \dots + m_n$$
乘法原理（分步计数）：若完成一件事需要 $n$ 个步骤，第 $i$ 步有 $m_i$ 种不同的方法，则完成这件事共有： $$N = m_1 \times m_2 \times \dots \times m_n$$

4.3 排列与组合

1. 公式与推导

排列数 $P(n, k)$（或表示为 $A_n^k$）：从 $n$ 个不同元素中取出 $k$ 个元素排成一列。 $$P(n, k) = n \times (n-1) \times \dots \times (n-k+1) = \frac{n!}{(n-k)!}$$
组合数 $C(n, k)$（或表示为 $\binom{n}{k}$）：从 $n$ 个不同元素中取出 $k$ 个元素组成一组，不考虑顺序。因为从 $k$ 个元素的组合中，可以产生 $k!$ 种不同的排列，所以： $$C(n, k) = \frac{P(n, k)}{k!} = \frac{n!}{k!(n-k)!}$$

2. 递推性质（杨辉三角的核心性质）

$$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$ * 证明（组合意义）：从 $n$ 个元素中选 $k$ 个，我们关注其中一个特定的元素 $x$。 * 若选中 $x$，则需从剩余的 $n-1$ 个元素中选 $k-1$ 个，方案数为 $\binom{n-1}{k-1}$。 * 若不选 $x$，则需从剩余的 $n-1$ 个元素中选 $k$ 个，方案数为 $\binom{n-1}{k}$。 * 根据加法原理，总方案数即为两部分之和。

3. C++14 实现（避免大数溢出的动态规划写法）

直接计算阶乘容易引发数值溢出。使用递推式或动态规划可以在计算中避免乘法产生的中途溢出。

#include <iostream>
#include <vector>

// 利用递推公式计算组合数 C(n, k)
auto select_combin(int n, int k) -> long long {
    if (k < 0 || k > n) return 0;
    if (k == 0 || k == n) return 1;
    if (k > n / 2) k = n - k; // 优化空间：利用对称性 C(n, k) == C(n, n-k)

    std::vector<long long> dp(k + 1, 0);
    dp[0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = std::min(i, k); j > 0; --j) {
            dp[j] = dp[j] + dp[j - 1];
        }
    }
    return dp[k];
}

4.4 杨辉三角 (Pascal's Triangle)

杨辉三角（或帕斯卡三角形）与二项式定理的展开系数紧密关联： $$(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k}b^k$$

1. C++14 打印杨辉三角

#include <iostream>
#include <vector>
#include <iomanip>

auto print_pascal_triangle(int rows) -> void {
    std::vector<std::vector<long long>> triangle(rows);
    for (int i = 0; i < rows; ++i) {
        triangle[i].resize(i + 1, 1);
        for (int j = 1; j < i; ++j) {
            triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
        }
    }

    // 格式化输出
    for (int i = 0; i < rows; ++i) {
        std::cout << std::string((rows - i) * 2, ' '); // 打印前置空格保持居中
        for (int j = 0; j <= i; ++j) {
            std::cout << std::setw(4) << triangle[i][j];
        }
        std::cout << std::endl;
    }
}

int main() {
    print_pascal_triangle(6);
    return 0;
}

5. 其他

5.1 ASCII 码

1. 核心映射区间

ASCII (American Standard Code for Information Interchange) 使用 7 位二进制数来表示 128 个字符。 * 数字字符 '0' - '9'：ASCII 范围 $48 \sim 57$ (十六进制 $0x30 \sim 0x39$) * 大写字母 'A' - 'Z'：ASCII 范围 $65 \sim 90$ (十六进制 $0x41 \sim 0x5A$) * 小写字母 'a' - 'z'：ASCII 范围 $97 \sim 122$ (十六进制 $0x61 \sim 0x7A$)

2. 位运算与高效转换

大写与小写字母在 ASCII 码上正好相差 32（即二进制下的 $2^5$，对应字符 ' ' 的 ASCII 码）。 * 大小写转换：可以通过与 $32$ 进行异或（^）来实现快速转换。 * 字符转数字：直接通过减去字符 '0' 来获得其整数值。

#include <iostream>

int main() {
    char lower = 'g';
    // 1. 小写转大写：利用位运算异或 32 (0x20)
    char upper = lower ^ 32; 
    std::cout << lower << " -> " << upper << std::endl; // 输出 g -> G

    // 2. 利用位运算与 223 (0xDF) 也可以将字符强制转大写
    char some_char = 'k';
    std::cout << static_cast<char>(some_char & 0xDF) << std::endl; // 输出 K

    // 3. 字符数字转数值
    char num_char = '7';
    int num_val = num_char - '0';
    std::cout << "Char '7' to int: " << num_val << std::endl; // 输出 7

    return 0;
}

6. 综合练习题与解析

练习题 1：进制转换与回文判定

题目描述：编写一个 C++14 函数，接收一个十进制正整数 $N$，将其转换为 $B$ 进制数（$2 \le B \le 16$），并判断该 $B$ 进制下的字符串表示是否为“回文串”（正读和反读都相同的字符串）。

C++14 实现与解析

#include <iostream>
#include <string>
#include <algorithm>

// 辅助函数：十进制转 B 进制
auto to_base(long long n, int b) -> std::string {
    const char table[] = "0123456789ABCDEF";
    std::string s = "";
    while (n > 0) {
        s += table[n % b];
        n /= b;
    }
    std::reverse(s.begin(), s.end());
    return s.empty() ? "0" : s;
}

// 判定回文
auto is_palindrome(const std::string& s) -> bool {
    int left = 0;
    int right = s.length() - 1;
    while (left < right) {
        if (s[left] != s[right]) return false;
        left++;
        right--;
    }
    return true;
}

int main() {
    long long n = 121;
    int base = 10;
    std::string representation = to_base(n, base);

    std::cout << "Number " << n << " in base " << base << " is: " << representation << std::endl;
    if (is_palindrome(representation)) {
        std::cout << "It is a palindrome!" << std::endl;
    } else {
        std::cout << "It is not a palindrome." << std::endl;
    }
    return 0;
}

解析：本题将进制转换与双指针字符串遍历技术相结合。在 to_base 中，通过不断对基数 $B$ 取余，自底向上构建目标字符串。由于最低位先出，构建完毕后需利用 std::reverse 反转。随后在 is_palindrome 中，使用左右指针从两端向中间汇聚，时间复杂度为 $O(\log_B N)$。

练习题 2：线性筛法求区间质数和

题目描述：输入一个整数 $M$，计算并输出 $[1, M]$ 区间内所有质数的累加和。由于数据范围可能较大，要求算法在 $O(M)$ 线性时间内完成。

C++14 实现与解析

#include <iostream>
#include <vector>
#include <numeric>

auto get_prime_sum(int m) -> long long {
    if (m < 2) return 0;
    std::vector<bool> is_prime(m + 1, true);
    std::vector<int> primes;
    is_prime[0] = is_prime[1] = false;

    long long sum = 0;
    for (int i = 2; i <= m; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
            sum += i; // 累加当前发现的质数
        }
        for (size_t j = 0; j < primes.size() && i * primes[j] <= m; ++j) {
            is_prime[i * primes[j]] = false;
            if (i % primes[j] == 0) {
                break; // 保证每个合数只被其最小质因数标记
            }
        }
    }
    return sum;
}

int main() {
    int m = 100'000; // 使用 C++14 数字分隔符
    std::cout << "Sum of primes up to " << m << " is " << get_prime_sum(m) << std::endl;
    return 0;
}

解析：相较于普通筛法的 $O(M \log \log M)$，线性筛通过 i % primes[j] == 0 这一关键逻辑控制，让每个合数都仅被其最小质因数标记。例如在遇到 4 之前，当 $i=2$，我们将 $2 \times 2 = 4$ 标为合数。当 $i=4$，由于 $4 \bmod 2 == 0$，程序会在筛选 $4 \times 3 = 12$ 前中断，从而避免了 $12$ 被重复筛选（$12$ 留到 $i=6$ 时被 $6 \times 2 = 12$ 所筛选）。这确保了整体时间复杂度严格在 $O(M)$ 内完成。

练习题 3：不相邻选球问题（组合数学应用）

题目描述：在一排 $N$ 个位置的网格中放入 $K$ 个完全相同的球（每个位置最多放一个球），要求任意两个球不能相邻，求有多少种摆放方案？

数学推导与证明

设方案数为 $S$。我们可以把放球后的状态抽象成“放了球的网格”与“未放球的网格”。 1. 首先，未放球的网格共有 $N - K$ 个。 2. 将这 $N - K$ 个未放球的网格排成一排。它们之间以及两端会形成一系列“空隙”，空隙的个数为 $(N - K) + 1$。 3. 如果我们将这 $K$ 个球塞入这些空隙中，由于每个空隙最多只能塞入一个球，这能确保任意两球绝不相邻。 4. 因此，问题等价于从这 $N - K + 1$ 个空隙中选择 $K$ 个位置放球： $$S = \binom{N - K + 1}{K}$$

C++14 实现与解析

#include <iostream>
#include <vector>

// 利用前面设计的动态规划 C(n, k) 求解
auto solve_non_adjacent(int n, int k) -> long long {
    if (k > (n + 1) / 2) return 0; // 鸽巢原理，若球数过多则必定有相邻
    return select_combin(n - k + 1, k);
}

int main() {
    int N = 10;
    int K = 4;
    std::cout << "Number of ways to place " << K << " balls in " << N 
              << " slots without being adjacent: " << solve_non_adjacent(N, K) << std::endl;
    return 0;
}

解析：该经典物理背景问题通过“插空法”将带有不相邻限制的计数转换成了常规无限制的组合数。在代码实现中，首先进行了边界剪枝：当 $K > \lfloor(N+1)/2\rfloor$ 时，由鸽巢原理可知，必定会有两球相邻，故直接返回 0。随后调用防溢出的 select_combin 进行高效求值。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com

入门组大纲2.1.5 数学与其他

C++14 编程与数学基础讲义

1. 数及其运算

1.1 自然数、整数、有理数、实数的四则运算

1. 概念与性质

2. C++14 精度与边界陷阱

浮点数安全比较方法

1.2 进制与转换：二、八、十、十六进制

1. 进制转换原理

2. C++14 代码实现

2. 初等数学

2.1 初中代数：一元二次方程及其求解

1. 公式推导

2. C++14 实现（支持实根与虚根判定）

2.2 初中几何：基本平面几何计算

1. 海伦公式 (Heron's Formula) 推导

2. C++14 三角形与圆计算实现

3. 初等数论

3.1 基础概念与除法性质

3.2 向下取整、模运算、取余

1. 定义

2. C++14 取模与向下取整性质

3.3 算术基本定理 (唯一分解定理)

1. 定理陈述与证明思路

2. C++14 实现：单个数的质因数分解

3.4 辗转相除法 (欧几里得算法)

1. 原理与证明

2. C++14 实现

3.5 素数筛法

1. 埃拉托斯特尼筛法 (Sieve of Eratosthenes)

2. 线性筛法 / 欧拉筛法 (Sieve of Euler)

3. C++14 两种筛法代码对比

4. 离散与组合数学

4.1 集合 (Sets)

1. 概念与运算

2. C++14 标准库操作

4.2 加法原理与乘法原理

4.3 排列与组合

1. 公式与推导

2. 递推性质（杨辉三角的核心性质）

3. C++14 实现（避免大数溢出的动态规划写法）

4.4 杨辉三角 (Pascal's Triangle)

1. C++14 打印杨辉三角

5. 其他

5.1 ASCII 码

1. 核心映射区间

2. 位运算与高效转换

6. 综合练习题与解析

练习题 1：进制转换与回文判定

C++14 实现与解析

练习题 2：线性筛法求区间质数和

C++14 实现与解析

练习题 3：不相邻选球问题（组合数学应用）

数学推导与证明

C++14 实现与解析