# 《北师大版五年级数学（奥数）与信奥（C++）双栖特训完整讲义》

## 课程总纲与概念映射

---

## 第一章：小数除法与循环小数 —— 计算机中的高精度除法

### 1.1 课内衔接与奥数拓展
在北师大版五上第一单元中，我们学习了小数除法。
*   **循环小数**：一个数的小数部分，从某一位起，一个数字或者几个数字依次不断重复出现。例如 $1 \div 3 = 0.333\dots = 0.\overline{3}$，$1 \div 7 = 0.\overline{142857}$（循环节长度为6）。
*   **奥数规律探究**：任意一个最简分数 $\frac{A}{B}$，其小数表示要么是有限小数，要么是循环小数。
    *   若分母 $B$ 的质因数只有 $2$ 或 $5$，则它必能化为**有限小数**。
    *   若分母 $B$ 含有 $2$ 和 $5$ 以外的质因数，则它必能化为**循环小数**。
*   **奥数问题**：如何确定分数 $\frac{1}{13}$ 展开为小数后，小数点后第 $100$ 位数字是多少？它的循环节长度是多少？

### 1.2 信奥算法建模：高精度模拟除法
在 C++ 中，单精度浮点数 `float` 和双精度浮点数 `double` 的精度有限（通常 `double` 只有 15~17 位有效数字）。如果要计算一个分数小数点后 100 位甚至 1000 位，直接使用 `double` 会产生严重的精度丢失。

**模拟竖式除法**：
1.  计算整数商：`A / B`。
2.  求余数：`r = A % B`。
3.  每次将余数乘 10 作为新的被除数，计算当前位的商：`digit = (r * 10) / B`。
4.  更新余数：`r = (r * 10) % B`。
5.  **寻找循环节**：在除法过程中，如果某一步产生的**余数**在之前已经出现过，那么从小数字上一次出现该余数的位置，到当前位置，就是这个小数的**循环节**。

### 1.3 C++ 核心代码实现

以下程序可以计算任意两个正整数相除的结果，精确到指定的位数，并且能够自动检测循环节的起始位置和循环节长度。

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

using namespace std;

// 模拟除法并检测循环节
void simulateDivision(int A, int B, int precision) {
    // 1. 输出整数部分
    cout << A << " / " << B << " = " << A / B;
    int remainder = A % B;
    if (remainder == 0) {
        cout << ".0 (有限小数)" << endl;
        return;
    }
    cout << ".";

// 用于记录已经出现过的余数及其在小数部分出现的位置
    // remainder_pos[r] 保存余数 r 第一次出现时在小数点后的第几位 (从 0 开始)
    // 初始化为 -1 代表未出现过。分母最大支持 10000 
    vector<int> remainder_pos(10005, -1);
    vector<int> digits; // 存储每一位小数商

int pos = 0;
    int cycle_start = -1; // 循环节开始位置
    int cycle_len = 0;    // 循环节长度

while (remainder != 0 && pos < precision) {
        // 如果当前余数之前出现过，说明找到了循环节
        if (remainder_pos[remainder] != -1) {
            cycle_start = remainder_pos[remainder];
            cycle_len = pos - cycle_start;
            break; // 停止计算，已经检测到循环
        }

// 记录当前余数的位置
        remainder_pos[remainder] = pos;

// 模拟竖式除法
        remainder *= 10;
        digits.push_back(remainder / B);
        remainder %= B;
        pos++;
    }

// 2. 输出小数部分
    for (int i = 0; i < pos; i++) {
        // 如果有循环节，在循环节前后加上括号方便阅读
        if (cycle_len > 0 && i == cycle_start) cout << "[";
        cout << digits[i];
        if (cycle_len > 0 && i == pos - 1) cout << "]";
    }

cout << endl;

if (cycle_len > 0) {
        cout << "检测到循环小数！" << endl;
        cout << "循环节开始于小数点后第 " << cycle_start + 1 << " 位" << endl;
        cout << "循环节长度为: " << cycle_len << endl;
    } else if (remainder == 0) {
        cout << "这是有限小数。" << endl;
    } else {
        cout << "在前 " << precision << " 位内未检测到完整循环。" << endl;
    }
}

int main() {
    int a, b, p;
    cout << "===== 循环小数高精度除法模拟 =====" << endl;
    cout << "请输入分子 A 和分母 B (如 1 7): ";
    cin >> a >> b;
    cout << "请输入最大保留的小数位数: ";
    cin >> p;

simulateDivision(a, b, p);
    return 0;
}
```

---

### 1.4 课后巩固与挑战

#### 【数学挑战题】
已知分数 $\frac{1}{13}$ 化为小数后是一个循环小数。
1.  求出它的循环节和循环节长度。
2.  求它小数点后面第 $100$ 位上的数字。

#### 【信奥编程题】
**题目描述**：输入两个正整数 $A, B$（其中 $1 \le A < B \le 1000$）。请编写程序，求出分数 $\frac{A}{B}$ 的循环节。如果该分数是有限小数，则输出 `Limited Decimal`。
*   **输入样例 1**：`1 7`
*   **输出样例 1**：`142857`
*   **输入样例 2**：`3 8`
*   **输出样例 2**：`Limited Decimal`

#### 【挑战题参考答案与 C++ 源码】
*   **数学挑战题答案**：
    1. $\frac{1}{13} = 0.\overline{076923}$。循环节为 `076923`，循环节长度为 $6$。
    2. 计算小数点后第 $100$ 位：$100 \div 6 = 16 \dots 4$。余数是 $4$，说明第 $100$ 位数字与循环节的第 $4$ 位数字相同，即为 `9`。

*   **信奥编程题 C++ 源码**：

```cpp
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int A, B;
    if (!(cin >> A >> B)) return 0;

vector<int> pos_of_rem(1005, -1);
    vector<int> digits;
    int rem = A % B;
    int pos = 0;
    int cycle_start = -1;

while (rem != 0) {
        if (pos_of_rem[rem] != -1) {
            cycle_start = pos_of_rem[rem];
            break;
        }
        pos_of_rem[rem] = pos;
        rem *= 10;
        digits.push_back(rem / B);
        rem %= B;
        pos++;
    }

if (rem == 0) {
        cout << "Limited Decimal" << endl;
    } else {
        // 输出循环节
        for (size_t i = cycle_start; i < digits.size(); i++) {
            cout << digits[i];
        }
        cout << endl;
    }
    return 0;
}
```

---

## 第二章：倍数与因数 —— 素数筛法与因数个数定理

### 2.1 课内衔接与奥数拓展
在北师大版五上第三单元中，我们学习了因数、倍数、质数与合数的基本定义。
*   **因数个数定理（奥数高频考点）**：
    如果一个合数 $N$ 可以分解质因数：$N = p_1^{a_1} \times p_2^{a_2} \times \dots \times p_k^{a_k}$（其中 $p_i$ 是两两不同的质数，$a_i$ 为它们对应的指数）。
    那么 $N$ 的所有正因数的个数为：
    $$S = (a_1 + 1) \times (a_2 + 1) \times \dots \times (a_k + 1)$$
    *   例如：$12 = 2^2 \times 3^1$。它的因数个数为 $(2+1) \times (1+1) = 6$ 个（分别是：1, 2, 3, 4, 6, 12）。
*   **哥德巴赫猜想**：每一个大于 $2$ 的偶数都可以拆写成两个质数的和。

### 2.2 信奥算法建模：埃拉托斯特尼筛法（Sieve of Eratosthenes）
在第一讲中我们学习了用“试除法”判断一个数是否为质数。然而，如果我们需要找出 $1$ 到 $N$ 范围内所有的质数（例如 $N=10^6$），对每个数都进行一次试除，时间复杂度会达到 $O(N\sqrt{N})$，效率低下。

**埃氏筛法原理**：
1.  初始化一个大小为 $N+1$ 的布尔数组，全部设为 `true`，代表所有数默认都是质数。
2.  从 $2$ 开始，如果发现 $i$ 是质数，就将所有 $i$ 的倍数（$2i, 3i, 4i \dots$）全部标记为合数（`false`）。
3.  继续向后寻找，未被标记的数就是质数。
4.  **复杂度优化**：将时间复杂度降低到 $O(N \log \log N)$，可以在一瞬间求出百万级别范围内的质数。

### 2.3 C++ 核心代码实现

以下代码实现了埃氏筛法，并利用因数个数定理计算了一个数的所有因数个数。

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

using namespace std;

const int MAXN = 1000000;
bool is_prime[MAXN + 5];
vector<int> primes; // 存储筛选出来的所有质数

// 埃氏筛法：筛选出 1 到 n 范围内的所有质数
void sieve(int n) {
    fill(is_prime, is_prime + n + 1, true);
    is_prime[0] = is_prime[1] = false;

for (int i = 2; i * i <= n; i++) {
        if (is_prime[i]) {
            // 从 i*i 开始标记，因为 2*i, 3*i 已经被更小的质数标记过了
            for (int j = i * i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }

// 收集所有质数
    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
        }
    }
}

// 利用因数个数定理求一个数的因数个数
int countDivisors(int n) {
    int total_divisors = 1;
    int temp = n;

// 对 temp 进行质因数分解
    for (int p : primes) {
        if (p * p > temp) break; // 质因数不可能大于根号 temp
        if (temp % p == 0) {
            int exponent = 0;
            while (temp % p == 0) {
                exponent++;
                temp /= p;
            }
            // 根据定理，因数个数乘上 (指数 + 1)
            total_divisors *= (exponent + 1);
        }
    }
    // 如果 temp 最终仍大于 1，说明它本身就是一个质数（对应的指数为 1）
    if (temp > 1) {
        total_divisors *= (1 + 1);
    }
    return total_divisors;
}

int main() {
    // 预处理筛选出 1000000 以内的质数
    sieve(MAXN);

int num;
    cout << "===== 质因数分解与因数个数计算器 =====" << endl;
    cout << "请输入一个正整数 (1 - 1000000): ";
    cin >> num;

if (num < 1 || num > MAXN) {
        cout << "超出计算范围！" << endl;
        return 0;
    }

cout << num << " 的因数个数为: " << countDivisors(num) << " 个。" << endl;
    return 0;
}
```

---

### 2.4 课后巩固与挑战

#### 【数学挑战题】
已知一个正整数 $N = 2^3 \times 3^2 \times 5^1$。
1.  求出 $N$ 的具体数值。
2.  利用因数个数定理计算 $N$ 一共有多少个正因数。

#### 【信奥编程题】
**题目描述**：输入一个正整数 $M$（$1 \le M \le 10000$）。请编写程序找出在 $1$ 到 $M$ 之间，因数个数最多的那个数。如果有多个数的因数个数相同，输出数值最小的那一个。
*   **输入样例**：`12`
*   **输出样例**：
    ```text
    12 有最多因数，因数个数为: 6
    ```
    *解释*：$12$ 有 6 个因数（1, 2, 3, 4, 6, 12）；而 1 到 12 中，其他数的因数个数都少于 6。

#### 【挑战题参考答案与 C++ 源码】
*   **数学挑战题答案**：
    1. $N = 8 \times 9 \times 5 = 360$。
    2. 指数分别为 $3, 2, 1$。根据因数个数定理，因数总数为 $(3 + 1) \times (2 + 1) \times (1 + 1) = 4 \times 3 \times 2 = 24$ 个。

*   **信奥编程题 C++ 源码**：

```cpp
#include <iostream>
#include <vector>
using namespace std;

// 埃氏筛
vector<int> primes;
bool is_prime[20005];

void sieve(int n) {
    fill(is_prime, 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;
        }
    }
    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) primes.push_back(i);
    }
}

int getDivisorsCount(int n) {
    int ans = 1;
    int temp = n;
    for (int p : primes) {
        if (p * p > temp) break;
        if (temp % p == 0) {
            int cnt = 0;
            while (temp % p == 0) {
                cnt++;
                temp /= p;
            }
            ans *= (cnt + 1);
        }
    }
    if (temp > 1) ans *= 2;
    return ans;
}

int main() {
    int M;
    if (!(cin >> M)) return 0;
    sieve(20000);

int max_divisors = 0;
    int best_num = 1;

for (int i = 1; i <= M; i++) {
        int cnt = getDivisorsCount(i);
        if (cnt > max_divisors) {
            max_divisors = cnt;
            best_num = i;
        }
    }

cout << best_num << " 有最多因数，因数个数为: " << max_divisors << endl;
    return 0;
}
```

---

## 第三章：分数的意义与最简分数 —— 辗转相除法与高精度分数加减法

### 3.1 课内衔接与奥数拓展
在北师大版五上第五单元与五下第一单元中，我们学习了：
*   **约分**：运用分数的性质，把一个分数的分子、分母同时除以公因数。
*   **最简分数**：分子与分母互质。
*   **异分母分数加减法**：先通分，将分母化为相同的公分母（两个分母的**最小公倍数**），然后再进行分子加减。

**奥数思考**：
*   **最大公约数（GCD）与最小公倍数（LCM）的关系**：对于任意两个正整数 $a$ 和 $b$：
    $$\gcd(a, b) \times \text{lcm}(a, b) = a \times b$$
*   **辗转相除法定理**：$\gcd(a, b) = \gcd(b, a \bmod b)$。

### 3.2 信奥算法建模：面向对象思想与分数结构体（Struct）
在 C++ 编程中，没有原生的“分数”数据类型。我们可以使用 `struct`（结构体）将分子和分母封装在一起，建立一个名为 `Fraction` 的新数据类型，并为它编写**约分**、**加法**、**减法**等函数。

### 3.3 C++ 核心代码实现

以下程序实现了一个完整的“高精度分数计算器”，支持两个异分母分数精确的加减法运算，并自动约分为最简分数或整数。

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

using namespace std;

// 辗转相除法求最大公约数
long long gcd(long long a, long long b) {
    a = abs(a);
    b = abs(b);
    while (b != 0) {
        long long temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}

// 结构体：表示分数
struct Fraction {
    long long num; // 分子 (numerator)
    long long den; // 分母 (denominator)

// 构造函数：初始化分数并自动约分
    Fraction(long long n = 0, long long d = 1) {
        if (d == 0) {
            num = 0;
            den = 1;
            return;
        }
        // 处理负号：统一让分母保持正数
        if (d < 0) {
            n = -n;
            d = -d;
        }
        long long g = gcd(n, d);
        num = n / g;
        den = d / g;
    }

// 打印分数的辅助函数
    void print() const {
        if (den == 1) {
            cout << num;
        } else {
            cout << num << "/" << den;
        }
    }
};

// 分数加法：a/b + c/d = (a*d + c*b) / (b*d)
Fraction add(Fraction f1, Fraction f2) {
    long long new_num = f1.num * f2.den + f2.num * f1.den;
    long long new_den = f1.den * f2.den;
    return Fraction(new_num, new_den); // 构造时会自动调用 gcd 约分
}

// 分数减法：a/b - c/d = (a*d - c*b) / (b*d)
Fraction sub(Fraction f1, Fraction f2) {
    long long new_num = f1.num * f2.den - f2.num * f1.den;
    long long new_den = f1.den * f2.den;
    return Fraction(new_num, new_den);
}

int main() {
    long long n1, d1, n2, d2;
    cout << "===== 高精度分数计算器 =====" << endl;
    cout << "请输入第一个分数的分子和分母 (如 1 3 代表 1/3): ";
    cin >> n1 >> d1;
    cout << "请输入第二个分数的分子和分母 (如 1 6 代表 1/6): ";
    cin >> n2 >> d2;

Fraction f1(n1, d1);
    Fraction f2(n2, d2);

Fraction sum = add(f1, f2);
    Fraction diff = sub(f1, f2);

cout << "分数 1: "; f1.print(); cout << endl;
    cout << "分数 2: "; f2.print(); cout << endl;

cout << "它们的和为: "; sum.print(); cout << endl;
    cout << "它们的差为: "; diff.print(); cout << endl;

return 0;
}
```

---

### 3.4 课后巩固与挑战

#### 【数学挑战题】
已知两个分数 $\frac{5}{12}$ 与 $\frac{7}{18}$。
1.  求出它们分母的最小公倍数。
2.  计算 $\frac{5}{12} + \frac{7}{18}$ 的和，并约分为最简分数。

#### 【信奥编程题】
**题目描述**：古埃及人只使用分子为 $1$ 的分数（称为**单位分数**或**埃及分数**）。奥数中的一个经典问题是将一个分数拆分为若干个不同的单位分数之和。
请编写程序，输入一个最简真分数 $\frac{A}{B}$（$1 \le A < B \le 100$），利用“斐波那契贪心法”将它分解为若干个不同的埃及分数之和。
*   **贪心法步骤**：
    对于分数 $\frac{A}{B}$，设 $C = \lceil B/A \rceil$（即 $B/A$ 向上取整）。最大的不超过 $\frac{A}{B}$ 的单位分数就是 $\frac{1}{C}$。
    然后计算余下的部分：$\frac{A}{B} - \frac{1}{C}$，继续重复上述步骤，直到分子变为 $1$ 为止。
*   **输入样例**：`8 11`
*   **输出样例**：`1/2 + 1/5 + 1/37 + 1/4070`

#### 【挑战题参考答案与 C++ 源码】
*   **数学挑战题答案**：
    1. $12 = 2^2 \times 3$，$18 = 2 \times 3^2$。最小公倍数为 $2^2 \times 3^2 = 36$。
    2. 通分：$\frac{5}{12} + \frac{7}{18} = \frac{15}{36} + \frac{14}{36} = \frac{29}{36}$。

*   **信奥编程题 C++ 源码**：

```cpp
#include <iostream>
using namespace std;

// 辗转相除
long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    long long A, B;
    if (!(cin >> A >> B)) return 0;

long long g = gcd(A, B);
    A /= g; B /= g;

bool first = true;
    while (A > 1) {
        // 计算 C = ceil(B/A) -> (B + A - 1) / A
        long long C = (B + A - 1) / A;
        
        if (!first) cout << " + ";
        cout << "1/" << C;
        first = false;

// 计算新分数: A/B - 1/C = (A*C - B) / (B*C)
        long long next_A = A * C - B;
        long long next_B = B * C;
        long long ng = gcd(next_A, next_B);
        A = next_A / ng;
        B = next_B / ng;
    }
    
    if (A == 1) {
        if (!first) cout << " + ";
        cout << "1/" << B;
    }
    cout << endl;

return 0;
}
```

---

## 第四章：几何特征与面积 —— 割补法与格点多边形皮克定理

### 4.1 课内衔接与奥数拓展
在北师大版五上第四、六单元中，我们学习了平行四边形、三角形和梯形的面积公式，以及复杂的组合图形面积计算。
*   **割补法与相减法**：把复杂的、不规则的图形分割成容易计算的小图形，或者补成一个大图形再减去多余的部分。

**奥数拓展：皮克定理（Pick's Theorem）**
在格点直角坐标系（每一个格点都是整数点）中，如果一个多边形的顶点都在格点上，那么这个多边形的面积 $S$ 与多边形内部的格点数 $I$、多边形边界上的格点数 $B$ 之间，存在如下美妙的数学关系：
$$S = I + \frac{B}{2} - 1$$

*   例如：格点三角形内部有 $3$ 个点（$I=3$），边界上有 $4$ 个点（$B=4$）。它的面积为 $S = 3 + 4/2 - 1 = 4$。

### 4.2 信奥算法建模：利用最大公约数求边界格点数
要在计算机中应用皮克定理，最难的部分是确定边界上的格点数 $B$。

**数论性质**：
对于平面上任意两个整点 $P_1(x_1, y_1)$ 和 $P_2(x_2, y_2)$，由它们连接而成的线段上（包含两端点）的格点数等于：
$$\gcd(|x_1 - x_2|, |y_1 - y_2|) + 1$$

通过这个公式，我们可以遍历多边形所有的边，计算出每一条边上的格点数，最后求和得到多边形边界上的总格点数 $B$。结合多边形面积算法（**鞋带公式/叉积面积法**），还可以反推出内部的格点数 $I$。

### 4.3 C++ 核心代码实现

以下程序输入三角形在格点纸上的三个顶点坐标，自动计算其边界点数、面积以及内部格点数。

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

using namespace std;

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

// 求两整点连线段上的格点数(排除终点，防止在环形累加中重复计算)
long long getBoundaryPointsOfSegment(long long x1, long long y1, long long x2, long long y2) {
    return gcd(x1 - x2, y1 - y2);
}

int main() {
    long long x1, y1, x2, y2, x3, y3;
    cout << "===== 格点三角形几何计算器 (皮克定理) =====" << endl;
    cout << "请依次输入三角形三个顶点 A, B, C 的坐标 (x y): " << endl;
    cout << "A 的坐标 (如 0 0): "; cin >> x1 >> y1;
    cout << "B 的坐标 (如 0 3): "; cin >> x2 >> y2;
    cout << "C 的坐标 (如 4 0): "; cin >> x3 >> y3;

// 1. 利用向量叉积计算多边形面积的两倍 (避免浮点数精度问题)
    // 2 * S = |x1(y2 - y3) + x2(y3 - y1) + x3(y1 - y2)|
    long long twice_area = abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2));
    double area = twice_area / 2.0;

// 2. 累加三条边上的格点数得到边界总格点数 B
    // 每次只算起点，排除终点，刚好把所有顶点各算一次
    long long B = getBoundaryPointsOfSegment(x1, y1, x2, y2) +
                  getBoundaryPointsOfSegment(x2, y2, x3, y3) +
                  getBoundaryPointsOfSegment(x3, y3, x1, y1);

// 3. 根据皮克定理：S = I + B/2 - 1 => 2*S = 2*I + B - 2 => 2*I = 2*S - B + 2
    long long I = (twice_area - B + 2) / 2;

cout << "--------------------------------------------" << endl;
    cout << "计算结果如下：" << endl;
    cout << "三角形面积 S = " << area << endl;
    cout << "边界格点数 B = " << B << " 个" << endl;
    cout << "内部格点数 I = " << I << " 个" << endl;

return 0;
}
```

---

### 4.4 课后巩固与挑战

#### 【数学挑战题】
已知一个格点矩形，其四个顶点坐标分别为 $(0,0), (6,0), (6,4), (0,4)$。
1.  求出这个矩形的面积 $S$。
2.  求出边界格点数 $B$ 与内部格点数 $I$。
3.  代入皮克定理公式，验证其是否成立。

#### 【信奥编程题】
**题目描述**：输入一个三角形的三个格点顶点坐标。已知它内部没有其他格点（即 $I = 0$）。
请问这样的三角形，其边界点数 $B$ 最小是多少？并编写程序，判定任意输入的格点三角形是否属于这种“无内点三角形”。如果是，输出它的面积和边界点数。
*   **输入样例**：`0 0 1 0 0 1`
*   **输出样例**：
    ```text
    这属于无内点三角形！
    它的面积 S = 0.5
    边界格点数 B = 3
    ```

#### 【挑战题参考答案与 C++ 源码】
*   **数学挑战题答案**：
    1. 矩形长为 $6$，宽为 $4$，面积 $S = 6 \times 4 = 24$。
    2. 边界上的格点：
       * 两条横边各含有 $7$ 个点。
       * 两条竖边各含有 $5$ 个点。
       * 重合四个顶点，所以 $B = 2 \times (6+1) + 2 \times (4+1) - 4 = 14 + 10 - 4 = 20$ 个。
       * 内部的点：$(1..5) \times (1..3) \implies I = 5 \times 3 = 15$ 个。
    3. 验证：$I + B/2 - 1 = 15 + 20/2 - 1 = 15 + 10 - 1 = 24$。面积一致，定理成立。

*   **信奥编程题 C++ 源码**：

```cpp
#include <iostream>
#include <cmath>
using namespace std;

long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    long long x1, y1, x2, y2, x3, y3;
    if (!(cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3)) return 0;

long long twice_area = abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2));
    long long B = gcd(x1 - x2, y1 - y2) + gcd(x2 - x3, y2 - y3) + gcd(x3 - x1, y3 - y1);
    long long I = (twice_area - B + 2) / 2;

if (I == 0) {
        cout << "这属于无内点三角形！" << endl;
        cout << "它的面积 S = " << twice_area / 2.0 << endl;
        cout << "边界格点数 B = " << B << endl;
    } else {
        cout << "这不是无内点三角形。它内部有 " << I << " 个格点。" << endl;
    }

return 0;
}
```

---

## 第五章：逻辑、代数与状态空间 —— 列方程、鸡兔同笼与深度枚举

### 5.1 课内衔接与奥数拓展
在五下第七单元《用方程解决问题》中，我们学习了列一元一次方程、二元一次方程组来解决应用题。

**奥数拓展（多元不定方程）**：
课内的“鸡兔同笼”由于刚好有两个方程，存在唯一确定的确定解。但在实际奥数竞赛中，常常会有多于两个未知数的不定方程。
*   例如：“百钱买百鸡”，公鸡 $5$ 元/只，母鸡 $3$ 元/只，小鸡 $3$ 只/$1$ 元，要用 $100$ 元买 $100$ 只鸡。
*   **奥数规律**：这类题目我们无法直接求出唯一的方程代数解，需要结合题目的“整数限制”以及“范围不等式”进行试凑。

### 5.2 信奥算法建模：多维空间枚举与减枝（Pruning）
计算机在处理多变量不定方程时，核心思想是**枚举（Search）**。
若要寻找最省钱、最省时间或效益最大化的解，我们需要用循环遍历每一个可能的变量值。

**剪枝（Pruning）优化原理**：
1.  **减少无用循环**：如果买 $x$ 只公鸡已经超过了 $100$ 元，循环就应当立刻终止。
2.  **变量关联替代**：若已知公鸡买 $x$ 只，母鸡买 $y$ 只，那么小鸡的数量必然是 $100 - x - y$，不需对小鸡再开一重循环。这属于利用约束关系直接降低算法复杂度（把 $O(N^3)$ 降为 $O(N^2)$）。

### 5.3 C++ 核心代码实现

以下程序是“百钱买百鸡”的升级版。除了打印所有的购买方案外，它还允许用户自定义商品价格，并在找到的可行方案中，找出“公鸡数量最多”的那一个最优解。

```cpp
#include <iostream>

using namespace std;

int main() {
    int total_money, total_count;
    cout << "===== 智能不定方程求解器 =====" << endl;
    cout << "请输入总钱数: "; cin >> total_money;
    cout << "请输入总购买数量: "; cin >> total_count;

// 自定义商品价格
    int p_rooster = 5;  // 公鸡 5 文
    int p_hen = 3;     // 母鸡 3 文
    // 小鸡 3只 1文。为避免小数乘除，我们在方程两边同乘以 3

int best_rooster = -1; // 记录公鸡数量最多的方案中，公鸡的数量
    int best_x = 0, best_y = 0, best_z = 0;
    int scheme_count = 0;

cout << "--------------------------------------------" << endl;
    cout << "可行购买方案列表：" << endl;

// 优化枚举上限：x * p_rooster 绝不可能超过 total_money
    for (int x = 0; x <= total_money / p_rooster; x++) {
        for (int y = 0; y <= total_money / p_hen; y++) {
            // 根据总数约束直接计算小鸡 z
            int z = total_count - x - y;
            if (z < 0) continue; // 小鸡数不能为负
            if (z % 3 != 0) continue; // 小鸡必须是 3 的倍数（因为3只1文钱）

// 价格等式：x * p_rooster + y * p_hen + z / 3 == total_money
            // 两边同乘以 3 转换为纯整数运算，避免精度误差：
            if (3 * p_rooster * x + 3 * p_hen * y + z == 3 * total_money) {
                scheme_count++;
                cout << "方案 " << scheme_count << ": "
                     << "公鸡 " << x << " 只, "
                     << "母鸡 " << y << " 只, "
                     << "小鸡 " << z << " 只" << endl;

// 更新公鸡数量最多的最优解
                if (x > best_rooster) {
                    best_rooster = x;
                    best_x = x;
                    best_y = y;
                    best_z = z;
                }
            }
        }
    }

cout << "--------------------------------------------" << endl;
    if (scheme_count > 0) {
        cout << "共找到 " << scheme_count << " 种可行方案。" << endl;
        cout << "其中公鸡数量最多的最优方案为：" << endl;
        cout << "公鸡: " << best_x << " 只，母鸡: " << best_y << " 只，小鸡: " << best_z << " 只" << endl;
    } else {
        cout << "在当前预算与数量限制下，无解！" << endl;
    }

return 0;
}
```

---

### 5.4 课后巩固与挑战

#### 【数学挑战题】
有一群三脚兽与四脚兽关在同一个笼子里。已知头一共有 $20$ 个，足一共有 $68$ 只。
1.  设三脚兽有 $x$ 只，四脚兽有 $y$ 只，请列出方程组。
2.  求出它们各自的数量。

#### 【信奥编程题】
**题目描述**：有三种包装的铅笔：
*   A 种包装：每盒 $3$ 支，售价 $5$ 元；
*   B 种包装：每盒 $5$ 支，售价 $8$ 元；
*   C 种包装：每盒 $10$ 支，售价 $15$ 元。
现在老师要购买**正好** $100$ 支铅笔，请问应该各买多少盒，才能使花钱最少？（要求：每种包装至少买一盒）。
编写程序，输出最省钱的购买组合及总费用。
*   **输出样例格式**：
    ```text
    最省钱方案: A种 1 盒, B种 1 盒, C种 9 盒, 最少花费: 148 元
    ```

#### 【挑战题参考答案与 C++ 源码】
*   **数学挑战题答案**：
    1. 方程组如下：
       $$x + y = 20$$
       $$3x + 4y = 68$$
    2. 代入消元法：由第一个方程得 $x = 20 - y$，代入第二个方程：
       $3(20 - y) + 4y = 68 \implies 60 - 3y + 4y = 68 \implies y = 8$。
       那么 $x = 20 - 8 = 12$。
       答：三脚兽有 $12$ 只，四脚兽有 $8$ 只。

*   **信奥编程题 C++ 源码**：

```cpp
#include <iostream>

using namespace std;

int main() {
    int target_pencils = 100;
    int min_cost = 1e9; // 初始化为一个很大的数
    int best_a = 0, best_b = 0, best_c = 0;

// a 代表 A 种盒数, b 代表 B 种盒数
    // 由于 3*a < 100 且至少买 1 盒
    for (int a = 1; a <= target_pencils / 3; a++) {
        for (int b = 1; b <= target_pencils / 5; b++) {
            int remaining = target_pencils - (3 * a + 5 * b);
            if (remaining <= 0) continue;
            
            // C 种包装每盒 10 支，所以剩余铅笔数必须是 10 的倍数
            if (remaining % 10 == 0) {
                int c = remaining / 10;
                if (c >= 1) { // 至少买一盒
                    int current_cost = 5 * a + 8 * b + 15 * c;
                    if (current_cost < min_cost) {
                        min_cost = current_cost;
                        best_a = a;
                        best_b = b;
                        best_c = c;
                    }
                }
            }
        }
    }

if (min_cost != 1e9) {
        cout << "最省钱方案: A种 " << best_a << " 盒, B种 " << best_b << " 盒, C种 " << best_c << " 盒, 最少花费: " << min_cost << " 元" << endl;
    } else {
        cout << "无解！" << endl;
    }

return 0;
}
```

《北师大版五年级数学（奥数）与信奥（C++）双栖特训完整讲义》

课程总纲与概念映射

北师大版课内单元	奥数拓展专题	信奥（C++）对应算法模型
五上第一单元：小数除法	循环小数的周期性与有理数性质	高精度除法模拟、余数定位法
五上第三单元：倍数与因数	因数个数定理与哥德巴赫猜想	埃拉托斯特尼筛法（素数筛）、试除优化
五上第五单元：分数的意义	约分、最简分数与分数的精确加减法	欧几里得算法（最大公约数）、结构体建模
五上第四/六单元：多边形面积	格点多边形、不规则割补法	皮克定理（Pick's Theorem）、高精度坐标计算
五下第七单元：用方程解决问题	鸡兔同笼变式、多元不定方程	双重循环枚举、减枝优化算法

第一章：小数除法与循环小数 —— 计算机中的高精度除法

1.1 课内衔接与奥数拓展

在北师大版五上第一单元中，我们学习了小数除法。 * 循环小数：一个数的小数部分，从某一位起，一个数字或者几个数字依次不断重复出现。例如 $1 \div 3 = 0.333\dots = 0.\overline{3}$，$1 \div 7 = 0.\overline{142857}$（循环节长度为6）。 * 奥数规律探究：任意一个最简分数 $\frac{A}{B}$，其小数表示要么是有限小数，要么是循环小数。 * 若分母 $B$ 的质因数只有 $2$ 或 $5$，则它必能化为有限小数。 * 若分母 $B$ 含有 $2$ 和 $5$ 以外的质因数，则它必能化为循环小数。 * 奥数问题：如何确定分数 $\frac{1}{13}$ 展开为小数后，小数点后第 $100$ 位数字是多少？它的循环节长度是多少？

1.2 信奥算法建模：高精度模拟除法

在 C++ 中，单精度浮点数 float 和双精度浮点数 double 的精度有限（通常 double 只有 15~17 位有效数字）。如果要计算一个分数小数点后 100 位甚至 1000 位，直接使用 double 会产生严重的精度丢失。

模拟竖式除法： 1. 计算整数商：A / B。 2. 求余数：r = A % B。 3. 每次将余数乘 10 作为新的被除数，计算当前位的商：digit = (r * 10) / B。 4. 更新余数：r = (r * 10) % B。 5. 寻找循环节：在除法过程中，如果某一步产生的余数在之前已经出现过，那么从小数字上一次出现该余数的位置，到当前位置，就是这个小数的循环节。

1.3 C++ 核心代码实现

以下程序可以计算任意两个正整数相除的结果，精确到指定的位数，并且能够自动检测循环节的起始位置和循环节长度。

#include <iostream>
#include <vector>

using namespace std;

// 模拟除法并检测循环节
void simulateDivision(int A, int B, int precision) {
    // 1. 输出整数部分
    cout << A << " / " << B << " = " << A / B;
    int remainder = A % B;
    if (remainder == 0) {
        cout << ".0 (有限小数)" << endl;
        return;
    }
    cout << ".";

    // 用于记录已经出现过的余数及其在小数部分出现的位置
    // remainder_pos[r] 保存余数 r 第一次出现时在小数点后的第几位 (从 0 开始)
    // 初始化为 -1 代表未出现过。分母最大支持 10000 
    vector<int> remainder_pos(10005, -1);
    vector<int> digits; // 存储每一位小数商

    int pos = 0;
    int cycle_start = -1; // 循环节开始位置
    int cycle_len = 0;    // 循环节长度

    while (remainder != 0 && pos < precision) {
        // 如果当前余数之前出现过，说明找到了循环节
        if (remainder_pos[remainder] != -1) {
            cycle_start = remainder_pos[remainder];
            cycle_len = pos - cycle_start;
            break; // 停止计算，已经检测到循环
        }

        // 记录当前余数的位置
        remainder_pos[remainder] = pos;

        // 模拟竖式除法
        remainder *= 10;
        digits.push_back(remainder / B);
        remainder %= B;
        pos++;
    }

    // 2. 输出小数部分
    for (int i = 0; i < pos; i++) {
        // 如果有循环节，在循环节前后加上括号方便阅读
        if (cycle_len > 0 && i == cycle_start) cout << "[";
        cout << digits[i];
        if (cycle_len > 0 && i == pos - 1) cout << "]";
    }

    cout << endl;

    if (cycle_len > 0) {
        cout << "检测到循环小数！" << endl;
        cout << "循环节开始于小数点后第 " << cycle_start + 1 << " 位" << endl;
        cout << "循环节长度为: " << cycle_len << endl;
    } else if (remainder == 0) {
        cout << "这是有限小数。" << endl;
    } else {
        cout << "在前 " << precision << " 位内未检测到完整循环。" << endl;
    }
}

int main() {
    int a, b, p;
    cout << "===== 循环小数高精度除法模拟 =====" << endl;
    cout << "请输入分子 A 和分母 B (如 1 7): ";
    cin >> a >> b;
    cout << "请输入最大保留的小数位数: ";
    cin >> p;

    simulateDivision(a, b, p);
    return 0;
}

1.4 课后巩固与挑战

【数学挑战题】

已知分数 $\frac{1}{13}$ 化为小数后是一个循环小数。 1. 求出它的循环节和循环节长度。 2. 求它小数点后面第 $100$ 位上的数字。

【信奥编程题】

题目描述：输入两个正整数 $A, B$（其中 $1 \le A < B \le 1000$）。请编写程序，求出分数 $\frac{A}{B}$ 的循环节。如果该分数是有限小数，则输出 Limited Decimal。 * 输入样例 1：1 7 * 输出样例 1：142857 * 输入样例 2：3 8 * 输出样例 2：Limited Decimal

【挑战题参考答案与 C++ 源码】

数学挑战题答案：
1. $\frac{1}{13} = 0.\overline{076923}$。循环节为 076923，循环节长度为 $6$。
2. 计算小数点后第 $100$ 位：$100 \div 6 = 16 \dots 4$。余数是 $4$，说明第 $100$ 位数字与循环节的第 $4$ 位数字相同，即为 9。
信奥编程题 C++ 源码：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int A, B;
    if (!(cin >> A >> B)) return 0;

    vector<int> pos_of_rem(1005, -1);
    vector<int> digits;
    int rem = A % B;
    int pos = 0;
    int cycle_start = -1;

    while (rem != 0) {
        if (pos_of_rem[rem] != -1) {
            cycle_start = pos_of_rem[rem];
            break;
        }
        pos_of_rem[rem] = pos;
        rem *= 10;
        digits.push_back(rem / B);
        rem %= B;
        pos++;
    }

    if (rem == 0) {
        cout << "Limited Decimal" << endl;
    } else {
        // 输出循环节
        for (size_t i = cycle_start; i < digits.size(); i++) {
            cout << digits[i];
        }
        cout << endl;
    }
    return 0;
}

第二章：倍数与因数 —— 素数筛法与因数个数定理

2.1 课内衔接与奥数拓展

在北师大版五上第三单元中，我们学习了因数、倍数、质数与合数的基本定义。 * 因数个数定理（奥数高频考点）：如果一个合数 $N$ 可以分解质因数：$N = p_1^{a_1} \times p_2^{a_2} \times \dots \times p_k^{a_k}$（其中 $p_i$ 是两两不同的质数，$a_i$ 为它们对应的指数）。那么 $N$ 的所有正因数的个数为： $$S = (a_1 + 1) \times (a_2 + 1) \times \dots \times (a_k + 1)$$ * 例如：$12 = 2^2 \times 3^1$。它的因数个数为 $(2+1) \times (1+1) = 6$ 个（分别是：1, 2, 3, 4, 6, 12）。 * 哥德巴赫猜想：每一个大于 $2$ 的偶数都可以拆写成两个质数的和。

2.2 信奥算法建模：埃拉托斯特尼筛法（Sieve of Eratosthenes）

在第一讲中我们学习了用“试除法”判断一个数是否为质数。然而，如果我们需要找出 $1$ 到 $N$ 范围内所有的质数（例如 $N=10^6$），对每个数都进行一次试除，时间复杂度会达到 $O(N\sqrt{N})$，效率低下。

埃氏筛法原理： 1. 初始化一个大小为 $N+1$ 的布尔数组，全部设为 true，代表所有数默认都是质数。 2. 从 $2$ 开始，如果发现 $i$ 是质数，就将所有 $i$ 的倍数（$2i, 3i, 4i \dots$）全部标记为合数（false）。 3. 继续向后寻找，未被标记的数就是质数。 4. 复杂度优化：将时间复杂度降低到 $O(N \log \log N)$，可以在一瞬间求出百万级别范围内的质数。

2.3 C++ 核心代码实现

以下代码实现了埃氏筛法，并利用因数个数定理计算了一个数的所有因数个数。

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 1000000;
bool is_prime[MAXN + 5];
vector<int> primes; // 存储筛选出来的所有质数

// 埃氏筛法：筛选出 1 到 n 范围内的所有质数
void sieve(int n) {
    fill(is_prime, is_prime + n + 1, true);
    is_prime[0] = is_prime[1] = false;

    for (int i = 2; i * i <= n; i++) {
        if (is_prime[i]) {
            // 从 i*i 开始标记，因为 2*i, 3*i 已经被更小的质数标记过了
            for (int j = i * i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }

    // 收集所有质数
    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
        }
    }
}

// 利用因数个数定理求一个数的因数个数
int countDivisors(int n) {
    int total_divisors = 1;
    int temp = n;

    // 对 temp 进行质因数分解
    for (int p : primes) {
        if (p * p > temp) break; // 质因数不可能大于根号 temp
        if (temp % p == 0) {
            int exponent = 0;
            while (temp % p == 0) {
                exponent++;
                temp /= p;
            }
            // 根据定理，因数个数乘上 (指数 + 1)
            total_divisors *= (exponent + 1);
        }
    }
    // 如果 temp 最终仍大于 1，说明它本身就是一个质数（对应的指数为 1）
    if (temp > 1) {
        total_divisors *= (1 + 1);
    }
    return total_divisors;
}

int main() {
    // 预处理筛选出 1000000 以内的质数
    sieve(MAXN);

    int num;
    cout << "===== 质因数分解与因数个数计算器 =====" << endl;
    cout << "请输入一个正整数 (1 - 1000000): ";
    cin >> num;

    if (num < 1 || num > MAXN) {
        cout << "超出计算范围！" << endl;
        return 0;
    }

    cout << num << " 的因数个数为: " << countDivisors(num) << " 个。" << endl;
    return 0;
}

2.4 课后巩固与挑战

【数学挑战题】

已知一个正整数 $N = 2^3 \times 3^2 \times 5^1$。 1. 求出 $N$ 的具体数值。 2. 利用因数个数定理计算 $N$ 一共有多少个正因数。

【信奥编程题】

题目描述：输入一个正整数 $M$（$1 \le M \le 10000$）。请编写程序找出在 $1$ 到 $M$ 之间，因数个数最多的那个数。如果有多个数的因数个数相同，输出数值最小的那一个。 * 输入样例：12 * 输出样例： text 12 有最多因数，因数个数为: 6 解释：$12$ 有 6 个因数（1, 2, 3, 4, 6, 12）；而 1 到 12 中，其他数的因数个数都少于 6。

【挑战题参考答案与 C++ 源码】

数学挑战题答案：
1. $N = 8 \times 9 \times 5 = 360$。
2. 指数分别为 $3, 2, 1$。根据因数个数定理，因数总数为 $(3 + 1) \times (2 + 1) \times (1 + 1) = 4 \times 3 \times 2 = 24$ 个。
信奥编程题 C++ 源码：

#include <iostream>
#include <vector>
using namespace std;

// 埃氏筛
vector<int> primes;
bool is_prime[20005];

void sieve(int n) {
    fill(is_prime, 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;
        }
    }
    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) primes.push_back(i);
    }
}

int getDivisorsCount(int n) {
    int ans = 1;
    int temp = n;
    for (int p : primes) {
        if (p * p > temp) break;
        if (temp % p == 0) {
            int cnt = 0;
            while (temp % p == 0) {
                cnt++;
                temp /= p;
            }
            ans *= (cnt + 1);
        }
    }
    if (temp > 1) ans *= 2;
    return ans;
}

int main() {
    int M;
    if (!(cin >> M)) return 0;
    sieve(20000);

    int max_divisors = 0;
    int best_num = 1;

    for (int i = 1; i <= M; i++) {
        int cnt = getDivisorsCount(i);
        if (cnt > max_divisors) {
            max_divisors = cnt;
            best_num = i;
        }
    }

    cout << best_num << " 有最多因数，因数个数为: " << max_divisors << endl;
    return 0;
}

第三章：分数的意义与最简分数 —— 辗转相除法与高精度分数加减法

3.1 课内衔接与奥数拓展

在北师大版五上第五单元与五下第一单元中，我们学习了： * 约分：运用分数的性质，把一个分数的分子、分母同时除以公因数。 * 最简分数：分子与分母互质。 * 异分母分数加减法：先通分，将分母化为相同的公分母（两个分母的最小公倍数），然后再进行分子加减。

奥数思考： * 最大公约数（GCD）与最小公倍数（LCM）的关系：对于任意两个正整数 $a$ 和 $b$： $$\gcd(a, b) \times \text{lcm}(a, b) = a \times b$$ * 辗转相除法定理：$\gcd(a, b) = \gcd(b, a \bmod b)$。

3.2 信奥算法建模：面向对象思想与分数结构体（Struct）

在 C++ 编程中，没有原生的“分数”数据类型。我们可以使用 struct（结构体）将分子和分母封装在一起，建立一个名为 Fraction 的新数据类型，并为它编写约分、加法、减法等函数。

3.3 C++ 核心代码实现

以下程序实现了一个完整的“高精度分数计算器”，支持两个异分母分数精确的加减法运算，并自动约分为最简分数或整数。

#include <iostream>
#include <cmath>

using namespace std;

// 辗转相除法求最大公约数
long long gcd(long long a, long long b) {
    a = abs(a);
    b = abs(b);
    while (b != 0) {
        long long temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}

// 结构体：表示分数
struct Fraction {
    long long num; // 分子 (numerator)
    long long den; // 分母 (denominator)

    // 构造函数：初始化分数并自动约分
    Fraction(long long n = 0, long long d = 1) {
        if (d == 0) {
            num = 0;
            den = 1;
            return;
        }
        // 处理负号：统一让分母保持正数
        if (d < 0) {
            n = -n;
            d = -d;
        }
        long long g = gcd(n, d);
        num = n / g;
        den = d / g;
    }

    // 打印分数的辅助函数
    void print() const {
        if (den == 1) {
            cout << num;
        } else {
            cout << num << "/" << den;
        }
    }
};

// 分数加法：a/b + c/d = (a*d + c*b) / (b*d)
Fraction add(Fraction f1, Fraction f2) {
    long long new_num = f1.num * f2.den + f2.num * f1.den;
    long long new_den = f1.den * f2.den;
    return Fraction(new_num, new_den); // 构造时会自动调用 gcd 约分
}

// 分数减法：a/b - c/d = (a*d - c*b) / (b*d)
Fraction sub(Fraction f1, Fraction f2) {
    long long new_num = f1.num * f2.den - f2.num * f1.den;
    long long new_den = f1.den * f2.den;
    return Fraction(new_num, new_den);
}

int main() {
    long long n1, d1, n2, d2;
    cout << "===== 高精度分数计算器 =====" << endl;
    cout << "请输入第一个分数的分子和分母 (如 1 3 代表 1/3): ";
    cin >> n1 >> d1;
    cout << "请输入第二个分数的分子和分母 (如 1 6 代表 1/6): ";
    cin >> n2 >> d2;

    Fraction f1(n1, d1);
    Fraction f2(n2, d2);

    Fraction sum = add(f1, f2);
    Fraction diff = sub(f1, f2);

    cout << "分数 1: "; f1.print(); cout << endl;
    cout << "分数 2: "; f2.print(); cout << endl;

    cout << "它们的和为: "; sum.print(); cout << endl;
    cout << "它们的差为: "; diff.print(); cout << endl;

    return 0;
}

3.4 课后巩固与挑战

【数学挑战题】

已知两个分数 $\frac{5}{12}$ 与 $\frac{7}{18}$。 1. 求出它们分母的最小公倍数。 2. 计算 $\frac{5}{12} + \frac{7}{18}$ 的和，并约分为最简分数。

【信奥编程题】

题目描述：古埃及人只使用分子为 $1$ 的分数（称为单位分数或埃及分数）。奥数中的一个经典问题是将一个分数拆分为若干个不同的单位分数之和。请编写程序，输入一个最简真分数 $\frac{A}{B}$（$1 \le A < B \le 100$），利用“斐波那契贪心法”将它分解为若干个不同的埃及分数之和。 * 贪心法步骤：对于分数 $\frac{A}{B}$，设 $C = \lceil B/A \rceil$（即 $B/A$ 向上取整）。最大的不超过 $\frac{A}{B}$ 的单位分数就是 $\frac{1}{C}$。然后计算余下的部分：$\frac{A}{B} - \frac{1}{C}$，继续重复上述步骤，直到分子变为 $1$ 为止。 * 输入样例：8 11 * 输出样例：1/2 + 1/5 + 1/37 + 1/4070

【挑战题参考答案与 C++ 源码】

数学挑战题答案：
1. $12 = 2^2 \times 3$，$18 = 2 \times 3^2$。最小公倍数为 $2^2 \times 3^2 = 36$。
2. 通分：$\frac{5}{12} + \frac{7}{18} = \frac{15}{36} + \frac{14}{36} = \frac{29}{36}$。
信奥编程题 C++ 源码：

#include <iostream>
using namespace std;

// 辗转相除
long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    long long A, B;
    if (!(cin >> A >> B)) return 0;

    long long g = gcd(A, B);
    A /= g; B /= g;

    bool first = true;
    while (A > 1) {
        // 计算 C = ceil(B/A) -> (B + A - 1) / A
        long long C = (B + A - 1) / A;

        if (!first) cout << " + ";
        cout << "1/" << C;
        first = false;

        // 计算新分数: A/B - 1/C = (A*C - B) / (B*C)
        long long next_A = A * C - B;
        long long next_B = B * C;
        long long ng = gcd(next_A, next_B);
        A = next_A / ng;
        B = next_B / ng;
    }

    if (A == 1) {
        if (!first) cout << " + ";
        cout << "1/" << B;
    }
    cout << endl;

    return 0;
}

第四章：几何特征与面积 —— 割补法与格点多边形皮克定理

4.1 课内衔接与奥数拓展

在北师大版五上第四、六单元中，我们学习了平行四边形、三角形和梯形的面积公式，以及复杂的组合图形面积计算。 * 割补法与相减法：把复杂的、不规则的图形分割成容易计算的小图形，或者补成一个大图形再减去多余的部分。

奥数拓展：皮克定理（Pick's Theorem） 在格点直角坐标系（每一个格点都是整数点）中，如果一个多边形的顶点都在格点上，那么这个多边形的面积 $S$ 与多边形内部的格点数 $I$、多边形边界上的格点数 $B$ 之间，存在如下美妙的数学关系： $$S = I + \frac{B}{2} - 1$$

例如：格点三角形内部有 $3$ 个点（$I=3$），边界上有 $4$ 个点（$B=4$）。它的面积为 $S = 3 + 4/2 - 1 = 4$。

4.2 信奥算法建模：利用最大公约数求边界格点数

要在计算机中应用皮克定理，最难的部分是确定边界上的格点数 $B$。

数论性质：对于平面上任意两个整点 $P_1(x_1, y_1)$ 和 $P_2(x_2, y_2)$，由它们连接而成的线段上（包含两端点）的格点数等于： $$\gcd(|x_1 - x_2|, |y_1 - y_2|) + 1$$

通过这个公式，我们可以遍历多边形所有的边，计算出每一条边上的格点数，最后求和得到多边形边界上的总格点数 $B$。结合多边形面积算法（鞋带公式/叉积面积法），还可以反推出内部的格点数 $I$。

4.3 C++ 核心代码实现

以下程序输入三角形在格点纸上的三个顶点坐标，自动计算其边界点数、面积以及内部格点数。

#include <iostream>
#include <cmath>

using namespace std;

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

// 求两整点连线段上的格点数(排除终点，防止在环形累加中重复计算)
long long getBoundaryPointsOfSegment(long long x1, long long y1, long long x2, long long y2) {
    return gcd(x1 - x2, y1 - y2);
}

int main() {
    long long x1, y1, x2, y2, x3, y3;
    cout << "===== 格点三角形几何计算器 (皮克定理) =====" << endl;
    cout << "请依次输入三角形三个顶点 A, B, C 的坐标 (x y): " << endl;
    cout << "A 的坐标 (如 0 0): "; cin >> x1 >> y1;
    cout << "B 的坐标 (如 0 3): "; cin >> x2 >> y2;
    cout << "C 的坐标 (如 4 0): "; cin >> x3 >> y3;

    // 1. 利用向量叉积计算多边形面积的两倍 (避免浮点数精度问题)
    // 2 * S = |x1(y2 - y3) + x2(y3 - y1) + x3(y1 - y2)|
    long long twice_area = abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2));
    double area = twice_area / 2.0;

    // 2. 累加三条边上的格点数得到边界总格点数 B
    // 每次只算起点，排除终点，刚好把所有顶点各算一次
    long long B = getBoundaryPointsOfSegment(x1, y1, x2, y2) +
                  getBoundaryPointsOfSegment(x2, y2, x3, y3) +
                  getBoundaryPointsOfSegment(x3, y3, x1, y1);

    // 3. 根据皮克定理：S = I + B/2 - 1 => 2*S = 2*I + B - 2 => 2*I = 2*S - B + 2
    long long I = (twice_area - B + 2) / 2;

    cout << "--------------------------------------------" << endl;
    cout << "计算结果如下：" << endl;
    cout << "三角形面积 S = " << area << endl;
    cout << "边界格点数 B = " << B << " 个" << endl;
    cout << "内部格点数 I = " << I << " 个" << endl;

    return 0;
}

4.4 课后巩固与挑战

【数学挑战题】

已知一个格点矩形，其四个顶点坐标分别为 $(0,0), (6,0), (6,4), (0,4)$。 1. 求出这个矩形的面积 $S$。 2. 求出边界格点数 $B$ 与内部格点数 $I$。 3. 代入皮克定理公式，验证其是否成立。

【信奥编程题】

题目描述：输入一个三角形的三个格点顶点坐标。已知它内部没有其他格点（即 $I = 0$）。请问这样的三角形，其边界点数 $B$ 最小是多少？并编写程序，判定任意输入的格点三角形是否属于这种“无内点三角形”。如果是，输出它的面积和边界点数。 * 输入样例：0 0 1 0 0 1 * 输出样例： text 这属于无内点三角形！它的面积 S = 0.5 边界格点数 B = 3

【挑战题参考答案与 C++ 源码】

数学挑战题答案：
1. 矩形长为 $6$，宽为 $4$，面积 $S = 6 \times 4 = 24$。
2. 边界上的格点：
3. 两条横边各含有 $7$ 个点。
4. 两条竖边各含有 $5$ 个点。
5. 重合四个顶点，所以 $B = 2 \times (6+1) + 2 \times (4+1) - 4 = 14 + 10 - 4 = 20$ 个。
6. 内部的点：$(1..5) \times (1..3) \implies I = 5 \times 3 = 15$ 个。
7. 验证：$I + B/2 - 1 = 15 + 20/2 - 1 = 15 + 10 - 1 = 24$。面积一致，定理成立。
信奥编程题 C++ 源码：

#include <iostream>
#include <cmath>
using namespace std;

long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    long long x1, y1, x2, y2, x3, y3;
    if (!(cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3)) return 0;

    long long twice_area = abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2));
    long long B = gcd(x1 - x2, y1 - y2) + gcd(x2 - x3, y2 - y3) + gcd(x3 - x1, y3 - y1);
    long long I = (twice_area - B + 2) / 2;

    if (I == 0) {
        cout << "这属于无内点三角形！" << endl;
        cout << "它的面积 S = " << twice_area / 2.0 << endl;
        cout << "边界格点数 B = " << B << endl;
    } else {
        cout << "这不是无内点三角形。它内部有 " << I << " 个格点。" << endl;
    }

    return 0;
}

第五章：逻辑、代数与状态空间 —— 列方程、鸡兔同笼与深度枚举

5.1 课内衔接与奥数拓展

在五下第七单元《用方程解决问题》中，我们学习了列一元一次方程、二元一次方程组来解决应用题。

奥数拓展（多元不定方程）：课内的“鸡兔同笼”由于刚好有两个方程，存在唯一确定的确定解。但在实际奥数竞赛中，常常会有多于两个未知数的不定方程。 * 例如：“百钱买百鸡”，公鸡 $5$ 元/只，母鸡 $3$ 元/只，小鸡 $3$ 只/$1$ 元，要用 $100$ 元买 $100$ 只鸡。 * 奥数规律：这类题目我们无法直接求出唯一的方程代数解，需要结合题目的“整数限制”以及“范围不等式”进行试凑。

5.2 信奥算法建模：多维空间枚举与减枝（Pruning）

计算机在处理多变量不定方程时，核心思想是枚举（Search）。若要寻找最省钱、最省时间或效益最大化的解，我们需要用循环遍历每一个可能的变量值。

剪枝（Pruning）优化原理： 1. 减少无用循环：如果买 $x$ 只公鸡已经超过了 $100$ 元，循环就应当立刻终止。 2. 变量关联替代：若已知公鸡买 $x$ 只，母鸡买 $y$ 只，那么小鸡的数量必然是 $100 - x - y$，不需对小鸡再开一重循环。这属于利用约束关系直接降低算法复杂度（把 $O(N^3)$ 降为 $O(N^2)$）。

5.3 C++ 核心代码实现

#include <iostream>

using namespace std;

int main() {
    int total_money, total_count;
    cout << "===== 智能不定方程求解器 =====" << endl;
    cout << "请输入总钱数: "; cin >> total_money;
    cout << "请输入总购买数量: "; cin >> total_count;

    // 自定义商品价格
    int p_rooster = 5;  // 公鸡 5 文
    int p_hen = 3;     // 母鸡 3 文
    // 小鸡 3只 1文。为避免小数乘除，我们在方程两边同乘以 3

    int best_rooster = -1; // 记录公鸡数量最多的方案中，公鸡的数量
    int best_x = 0, best_y = 0, best_z = 0;
    int scheme_count = 0;

    cout << "--------------------------------------------" << endl;
    cout << "可行购买方案列表：" << endl;

    // 优化枚举上限：x * p_rooster 绝不可能超过 total_money
    for (int x = 0; x <= total_money / p_rooster; x++) {
        for (int y = 0; y <= total_money / p_hen; y++) {
            // 根据总数约束直接计算小鸡 z
            int z = total_count - x - y;
            if (z < 0) continue; // 小鸡数不能为负
            if (z % 3 != 0) continue; // 小鸡必须是 3 的倍数（因为3只1文钱）

            // 价格等式：x * p_rooster + y * p_hen + z / 3 == total_money
            // 两边同乘以 3 转换为纯整数运算，避免精度误差：
            if (3 * p_rooster * x + 3 * p_hen * y + z == 3 * total_money) {
                scheme_count++;
                cout << "方案 " << scheme_count << ": "
                     << "公鸡 " << x << " 只, "
                     << "母鸡 " << y << " 只, "
                     << "小鸡 " << z << " 只" << endl;

                // 更新公鸡数量最多的最优解
                if (x > best_rooster) {
                    best_rooster = x;
                    best_x = x;
                    best_y = y;
                    best_z = z;
                }
            }
        }
    }

    cout << "--------------------------------------------" << endl;
    if (scheme_count > 0) {
        cout << "共找到 " << scheme_count << " 种可行方案。" << endl;
        cout << "其中公鸡数量最多的最优方案为：" << endl;
        cout << "公鸡: " << best_x << " 只，母鸡: " << best_y << " 只，小鸡: " << best_z << " 只" << endl;
    } else {
        cout << "在当前预算与数量限制下，无解！" << endl;
    }

    return 0;
}

5.4 课后巩固与挑战

【数学挑战题】

有一群三脚兽与四脚兽关在同一个笼子里。已知头一共有 $20$ 个，足一共有 $68$ 只。 1. 设三脚兽有 $x$ 只，四脚兽有 $y$ 只，请列出方程组。 2. 求出它们各自的数量。

【信奥编程题】

题目描述：有三种包装的铅笔： * A 种包装：每盒 $3$ 支，售价 $5$ 元； * B 种包装：每盒 $5$ 支，售价 $8$ 元； * C 种包装：每盒 $10$ 支，售价 $15$ 元。现在老师要购买正好 $100$ 支铅笔，请问应该各买多少盒，才能使花钱最少？（要求：每种包装至少买一盒）。编写程序，输出最省钱的购买组合及总费用。 * 输出样例格式： text 最省钱方案: A种 1 盒, B种 1 盒, C种 9 盒, 最少花费: 148 元

【挑战题参考答案与 C++ 源码】

数学挑战题答案：
1. 方程组如下： $$x + y = 20$$ $$3x + 4y = 68$$
2. 代入消元法：由第一个方程得 $x = 20 - y$，代入第二个方程： $3(20 - y) + 4y = 68 \implies 60 - 3y + 4y = 68 \implies y = 8$。那么 $x = 20 - 8 = 12$。答：三脚兽有 $12$ 只，四脚兽有 $8$ 只。
信奥编程题 C++ 源码：

#include <iostream>

using namespace std;

int main() {
    int target_pencils = 100;
    int min_cost = 1e9; // 初始化为一个很大的数
    int best_a = 0, best_b = 0, best_c = 0;

    // a 代表 A 种盒数, b 代表 B 种盒数
    // 由于 3*a < 100 且至少买 1 盒
    for (int a = 1; a <= target_pencils / 3; a++) {
        for (int b = 1; b <= target_pencils / 5; b++) {
            int remaining = target_pencils - (3 * a + 5 * b);
            if (remaining <= 0) continue;

            // C 种包装每盒 10 支，所以剩余铅笔数必须是 10 的倍数
            if (remaining % 10 == 0) {
                int c = remaining / 10;
                if (c >= 1) { // 至少买一盒
                    int current_cost = 5 * a + 8 * b + 15 * c;
                    if (current_cost < min_cost) {
                        min_cost = current_cost;
                        best_a = a;
                        best_b = b;
                        best_c = c;
                    }
                }
            }
        }
    }

    if (min_cost != 1e9) {
        cout << "最省钱方案: A种 " << best_a << " 盒, B种 " << best_b << " 盒, C种 " << best_c << " 盒, 最少花费: " << min_cost << " 元" << endl;
    } else {
        cout << "无解！" << endl;
    }

    return 0;
}

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

北师大版小学数学五年级+信奥讲义

《北师大版五年级数学（奥数）与信奥（C++）双栖特训完整讲义》

课程总纲与概念映射

第一章：小数除法与循环小数 —— 计算机中的高精度除法

1.1 课内衔接与奥数拓展

1.2 信奥算法建模：高精度模拟除法

1.3 C++ 核心代码实现

1.4 课后巩固与挑战

【数学挑战题】

【信奥编程题】

【挑战题参考答案与 C++ 源码】

第二章：倍数与因数 —— 素数筛法与因数个数定理

2.1 课内衔接与奥数拓展

2.2 信奥算法建模：埃拉托斯特尼筛法（Sieve of Eratosthenes）

2.3 C++ 核心代码实现

2.4 课后巩固与挑战

【数学挑战题】

【信奥编程题】

【挑战题参考答案与 C++ 源码】

第三章：分数的意义与最简分数 —— 辗转相除法与高精度分数加减法

3.1 课内衔接与奥数拓展

3.2 信奥算法建模：面向对象思想与分数结构体（Struct）

3.3 C++ 核心代码实现

3.4 课后巩固与挑战

【数学挑战题】

【信奥编程题】

【挑战题参考答案与 C++ 源码】

第四章：几何特征与面积 —— 割补法与格点多边形皮克定理

4.1 课内衔接与奥数拓展

4.2 信奥算法建模：利用最大公约数求边界格点数

4.3 C++ 核心代码实现

4.4 课后巩固与挑战

【数学挑战题】

【信奥编程题】

【挑战题参考答案与 C++ 源码】

第五章：逻辑、代数与状态空间 —— 列方程、鸡兔同笼与深度枚举

5.1 课内衔接与奥数拓展

5.2 信奥算法建模：多维空间枚举与减枝（Pruning）

5.3 C++ 核心代码实现

5.4 课后巩固与挑战

【数学挑战题】

【信奥编程题】

【挑战题参考答案与 C++ 源码】