P1763 埃及分数

题目描述

来源：BIO 1997 Round 1 Question 3

在古埃及，人们使用单位分数的和（形如 \(\dfrac{1}{a}\) 的，\(a\) 是正整数）表示一切有理数。如：\(\dfrac{2}{3} = \dfrac{1}{2} + \dfrac{1}{6}\)，但不允许 \(\dfrac{2}{3} = \dfrac{1}{3} + \dfrac{1}{3}\)，因为加数中有相同的。对于一个分数 \(\dfrac{a}{b}\)，表示方法有很多种，但是哪种最好呢？首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越好。如： $$ \begin{aligned} \frac{19}{45} &= \frac{1}{3} + \frac{1}{12} + \frac{1}{180}\ \frac{19}{45} &= \frac{1}{3} + \frac{1}{15} + \frac{1}{45}\ \frac{19}{45} &= \frac{1}{3} + \frac{1}{18} + \frac{1}{30}\ \frac{19}{45} &= \frac{1}{4} + \frac{1}{6} + \frac{1}{180}\ \frac{19}{45} &= \frac{1}{5} + \frac{1}{6} + \frac{1}{18}\ \end{aligned} $$ 最好的是最后一种，因为 \(\dfrac{1}{18}\) 比 \(\dfrac{1}{180}, \dfrac{1}{45}, \dfrac{1}{30}\) 都大。
注意，可能有多个最优解。如： $$ \begin{aligned} \frac{59}{211} &= \frac{1}{4} + \frac{1}{36} + \frac{1}{633} + \frac{1}{3798}\ \frac{59}{211} &= \frac{1}{6} + \frac{1}{9} + \frac{1}{633} + \frac{1}{3798}\ \end{aligned} $$ 由于方法一与方法二中，最小的分数相同，因此二者均是最优解。

给出 \(a,b\)，编程计算最好的表达方式。保证最优解满足：最小的分数 \(\ge \cfrac{1}{10^7}\)。

输入格式

一行两个整数，分别为 \(a\) 和 \(b\) 的值。

输出格式

输出若干个数，自小到大排列，依次是单位分数的分母。

输入输出样例 #1

输入 #1

19 45

输出 #1

5 6 18

说明/提示

\(1 \lt a \lt b \lt 1000\)

Tip

b站讲解

📌 题目分析

给定数据： * 两个正整数 \(a\) 和 \(b\) (\(1 \lt a \lt b \lt 1000\))，代表分数 \(\dfrac{a}{b}\)。 * 保证最优解中，最小的单位分数 \(\ge \cfrac{1}{10^7}\)。

要求：将 \(\dfrac{a}{b}\) 拆分成若干个互不相同的单位分数之和。 评判最优解的标准： 1. 加数个数最少。 2. 在加数个数相同的情况下，最小的单位分数越大越好（即最大的分母越小越好）。

👉 本质： 搜索问题，状态空间中的每一步是从剩余分数中减去一个单位分数。

👉 类型： 迭代加深搜索 (IDDFS / IDA*)。

---

🧠 解题思路

1️⃣ 为什么普通的 BFS 或 DFS 会惨败？

• BFS（广度优先搜索）：虽然 BFS 能天然保证最先找到的解是“加数最少”的，但由于我们每一层可以选择的单位分母有无数个（例如 \(\dfrac{1}{2}, \dfrac{1}{3}, \dots, \dfrac{1}{10^7}\)），BFS 的队列会瞬间被撑爆，直接 Memory Limit Exceeded (MLE)。
• DFS（深度优先搜索）：由于一个分数可以被无限拆分（比如 \(\dfrac{1}{2} = \dfrac{1}{3} + \dfrac{1}{6}\)，\(\dfrac{1}{3}\) 还能继续拆），DFS 会陷入无限深度的拆分中无法自拔，直接 Stack Overflow 或 Time Limit Exceeded (TLE)。

2️⃣ 迭代加深搜索 (IDDFS)：完美的救星

IDDFS 结合了 BFS 和 DFS 的优点。 我们人为设定一个最大搜索深度（即允许拆分的最多分数个数），从 \(1\) 开始逐渐递增。 在设定的最大深度下，我们使用 DFS 搜索。一旦在这个深度下找到了解，它绝对是加数最少的解。这样既避免了 BFS 的空间爆炸，又阻止了 DFS 掉入无底洞。

3️⃣ 核心剪枝魔法 (IDA* 的灵魂)

在搜索时，如果不加限制地枚举分母，依然会超时。我们需要严密的数学剪枝：

• 下界（剪枝 1）： 下一个单位分数 \(\dfrac{1}{i}\) 不能大于剩余的真实分数 \(\dfrac{a}{b}\)。即 \(\dfrac{1}{i} \le \dfrac{a}{b} \implies i \ge \lceil \dfrac{b}{a} \rceil\)。同时，分母必须递增，所以 \(i\) 还必须大于上一次选的分母。
• 上界（最强剪枝 2）： 假设当前还需要找 \(k\) 个单位分数。如果这 \(k\) 个分数全部取当前最大的 \(\dfrac{1}{i}\)，它们的和 \(k \times \dfrac{1}{i}\) 依然 \(\le \dfrac{a}{b}\)。 由于后面的分母必须严格递增，实际的面积只会比这更小，这意味着这条路永远不可能凑够 \(\dfrac{a}{b}\)！此时直接 break，剪掉整个分支。
• 最优解剪枝（剪枝 3）： 如果在当前深度已经找到了一组可行解，其最大的分母为 \(M\)。那么在接下来的搜索中，一旦发现当前的枚举的分母 \(i \ge M\)，立刻 break（因为题目要求最大分母越小越好，超过现有最优解的路径毫无意义）。

---

💻 C++代码

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

using namespace std;

typedef long long ll;

int max_depth;          // 迭代加深的当前限制深度
vector<ll> path;        // 搜索过程中当前的路径
vector<ll> best_path;   // 记录当前深度的最优解

// 求最大公约数，用于分数化简
ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 求满足 1/c <= a/b 的最小分母 c
ll get_first_denominator(ll a, ll b) {
    if (b % a == 0) return b / a;
    return b / a + 1;
}

// current_d: 当前正在寻找第几个单位分数 (1 ~ max_depth)
// a, b: 当前剩余的分子和分母
// min_d: 本次寻找的分母下界（保证分母严格递增）
bool dfs(int current_d, ll a, ll b, ll min_d) {
    // 边界条件：到达最后一层
    if (current_d == max_depth) {
        // 如果最后剩下的是一个合法的单位分数
        if (a == 1 && b >= min_d) {
            // 如果这是第一个解，或者比现有最优解的最后一个分母更小，则更新答案
            if (best_path.empty() || b < best_path.back()) {
                path.push_back(b);
                best_path = path;
                path.pop_back();
            }
            return true; // 报告找到了解
        }
        return false;
    }

    bool found = false;
    // 确定分母枚举的起点
    ll start = max(min_d, get_first_denominator(a, b));

    // 开始枚举当前分母 i
    for (ll i = start; ; i++) {
        // 【最强剪枝】如果剩余的所有名额都用最大的 1/i 填充，还是无法达到 a/b，说明 i 太大了，直接结束本层循环
        // (max_depth - current_d + 1) * 1/i <= a/b  =>  (max_depth - current_d + 1) * b <= a * i
        if (b * (max_depth - current_d + 1) <= a * i) {
            break;
        }

        // 【最优解剪枝】如果当前枚举的分母已经大于等于已知最优解的最大分母，直接放弃
        if (!best_path.empty() && i >= best_path.back()) {
            break;
        }

        path.push_back(i);

        // 计算剩余的分数：a/b - 1/i = (a*i - b) / (b*i)
        ll next_a = a * i - b;
        ll next_b = b * i;
        ll g = gcd(next_a, next_b); // 必须化简！防止下一层数据溢出

        // 递归进入下一层
        if (dfs(current_d + 1, next_a / g, next_b / g, i + 1)) {
            found = true;
        }

        path.pop_back(); // 回溯恢复现场
    }

    return found;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll a, b;
    if (!(cin >> a >> b)) return 0;

    ll g = gcd(a, b);
    a /= g; 
    b /= g;

    // 如果已经是单位分数，直接输出
    if (a == 1) {
        cout << b << "\n";
        return 0;
    }

    // 迭代加深搜索：逐渐放宽最大项数
    for (max_depth = 1; ; max_depth++) {
        path.clear();
        best_path.clear();

        // 如果在当前最大项数下找到了解，立刻结束（因为保证了项数最少）
        if (dfs(1, a, b, get_first_denominator(a, b))) {
            for (size_t i = 0; i < best_path.size(); i++) {
                cout << best_path[i] << (i == best_path.size() - 1 ? "" : " ");
            }
            cout << "\n";
            break; 
        }
    }

    return 0;
}

---

⚠️ 易错点

1. 整数溢出导致 RE/WA： 在做分数减法时 next_b = b * i，由于 \(i\) 最高可以达到 \(10^7\) 甚至更大，\(b \times i\) 极易突破 32 位整型极限 \(2 \times 10^9\)。如果不开 long long，必定会导致计算错乱。
2. 忘记化简分数： 在传递给下一层 dfs 之前，必须计算 gcd 并对 next_a 和 next_b 进行约分化简。如果不化简，分母会成倍膨胀，连 long long 也会在几步之内被挤爆。
3. 剪枝条件的正反面混淆： 很多同学在写上限剪枝时会写成 if (i > (max_depth - current_d + 1) * b / a)，这里因为 C++ 的整数除法会向下取整，直接除会导致精度丢失误杀正解。一定要将其转换为乘法 b * (...) <= a * i 来进行严格精确的比较。

---

🚀 一句话总结

应对无穷广度和深度的完美对策：利用 IDDFS 限制深度保证加数最少，
用数学不等式极限剪枝保证搜索不超时！

---

🔥 补充：硬核知识点

贪心算法在埃及分数中的局限性

如果你去查阅古埃及分数的历史，你会发现意大利数学家斐波那契（Fibonacci，没错就是那个数列的发现者）和英国数学家西尔维斯特（Sylvester）曾提出过一个著名的贪心算法： 每一次都去减去不大于剩余分数的最大单位分数（也就是代码中的 get_first_denominator）。

比如我们要拆分 \(\dfrac{19}{45}\)： * 第一步找不大于它的最大单位分数：\(\dfrac{1}{3}\)。剩余 \(\dfrac{19}{45} - \dfrac{1}{3} = \dfrac{4}{45}\)。 * 第二步找最大单位分数：\(\dfrac{1}{12}\)。剩余 \(\dfrac{4}{45} - \dfrac{1}{12} = \dfrac{1}{180}\)。 * 第三步就是 \(\dfrac{1}{180}\)。 最终得出 \(\dfrac{19}{45} = \dfrac{1}{3} + \dfrac{1}{12} + \dfrac{1}{180}\)。

那为什么这道题不能用贪心？ 斐波那契贪心法虽然能保证在有限步内结束，但它得到的解往往不是项数最少的，也不是最小分数最大的！ 就如题目描述中指出的，\(\dfrac{1}{5} + \dfrac{1}{6} + \dfrac{1}{18}\) 是远比贪心解 \(\dfrac{1}{3} + \dfrac{1}{12} + \dfrac{1}{180}\) 更好（分母更小、更均匀）的方案。这就是为什么算法竞赛中必须祭出带有严密剪枝的 IDA* 算法的原因。