「一本通 1.3 练习 1」埃及分数

形式化题目

给定正整数 $a, b$ （满足 $0 < a < b < 1000$ 且 $\gcd(a, b) = 1$ ），求一组正整数序列 $x_1 < x_2 < \dots < x_k$ 使得：

\frac{a}{b} = \sum_{i=1}^k \frac{1}{x_i}

使得满足以下评价标准的解最优：

项数 $k$ 最小；
在 $k$ 最小的前提下，最大分母 $x_k$ 最小（对应最小的分数 $\frac{1}{x_k}$ 最大）；
若最大分母仍相同，分母序列的字典序最小。

输出按升序排列的分母序列 $x_1, x_2, \dots, x_k$ 。

正解

思路

本题是经典的迭代加深搜索（IDA*）与数学剪枝问题。

1. 为什么采用 IDA*？

题目首先要求加数个数 $k$ 尽可能少。如果使用普通的深度优先搜索（DFS），搜索深度可能无限延伸或陷在很深的分支中；如果使用广度优先搜索（BFS），由于状态分支多且状态记录占用内存巨大，极易出现内存超限（MLE）。因此，我们限制搜索深度 $limit = 1, 2, 3, \dots$ 逐层加深（IDA*）：

只要在某一层深度 $limit$ 找到了可行解，该深度即为项数最少的全局最优项数；
在同一层内，遍历所有可能解并更新最优解，即可保证选出最大分母最小、字典序最小的答案。

2. 搜索分支上下界推导与剪枝

假设当前正在搜索第 $limit - k + 1$ 项，还剩余 $k$ 项未确定，剩余需要凑出的分数为 $\frac{a}{b}$ ，上一项确定的分母为 $last$ 。当前待选分母设为 $x$ ：

下界（ $lo$ ）：
- 题目要求分母严格递增，故 $x \ge last + 1$ 。
- 当剩余项数 $k > 1$ 时，若选择的单位分数 $\frac{1}{x} \ge \frac{a}{b}$ ，后续继续相加必将超出目标分数。因此 $\frac{1}{x} < \frac{a}{b} \implies x > \frac{b}{a} \implies x \ge \lfloor \frac{b}{a} \rfloor + 1$ 。
- 综合得到下界： $lo = \max(last + 1, \lfloor \frac{b}{a} \rfloor + 1)$ 。
上界（ $hi$ ）：
- 剩余未确定的分母必须严格递增，因此后续的每个分数都严格小于当前分数，即 $\frac{1}{x_i} < \frac{1}{x}$ 。
- 即使剩下的 $k$ 个数都取到最大可能值（极限近似 $\frac{1}{x}$ ），它们的和也不会超过 $k \times \frac{1}{x} = \frac{k}{x}$ 。
- 如果 $\frac{k}{x} < \frac{a}{b}$ ，则即使剩下全部取当前最大可能值，其总和也无法凑齐剩余的 $\frac{a}{b}$ 。
- 因此必须满足 $\frac{k}{x} \ge \frac{a}{b} \implies x \le \lfloor \frac{k \cdot b}{a} \rfloor$ 。
- 综合得到上界： $hi = \lfloor \frac{k \cdot b}{a} \rfloor$ 。
叶子节点常数优化（ $k = 1$ ）：
- 当只剩下最后一项（ $k = 1$ ）时，不再进行循环枚举，而是直接判断 $\frac{1}{x} = \frac{a}{b}$ 是否成立。
- 此时 $x = \frac{b}{a}$ ，必须满足 $b \pmod a == 0$ 且 $x > last$ 。若成立，则直接得到一组可行解。

代码

Python 版：

python

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 10:54
# update_at: 2026-09-30 10:54

import sys
from math import gcd


def egypt_search(a: int, b: int, limit: int) -> tuple[int, ...] | None:
    """用恰好 limit 个互不相同的单位分数凑出 a/b，返回分母序列最优的一组，无解返回 None。

    序列比较规则：先比最大分母（越小则最小的分数 1/x_k 越大），
    再把整个分母序列从小到大做字典序比较，越小越优。
    """
    best: tuple[int, ...] | None = None

    def dfs(k: int, a: int, b: int, last: int, chosen: list[int]) -> None:
        """还剩 k 个加数要凑出 a/b，已选分母都小于等于 last，chosen 是当前路径。"""
        nonlocal best
        if k == 1:
            # 只剩一个加数时必须恰好相等：1/x = a/b ⟺ x = b/a（要求 b 是 a 的倍数）
            if b % a == 0:
                x = b // a
                if x > last:
                    seq = tuple(chosen + [x])
                    # (最大分母, 整个序列) 一起比：先保最大分母最小，再保字典序最小
                    if best is None or (seq[-1], seq) < (best[-1], best):
                        best = seq
            return
        lo = max(last + 1, b // a + 1)  # 1/x ≥ a/b 会立刻超额或把余量取空，排除
        hi = k * b // a                 # 连 k 个 1/x 都凑不满 a/b 的分母，排除
        for x in range(lo, hi + 1):
            na, nb = a * x - b, b * x   # a/b - 1/x = (ax-b)/(bx)
            g = gcd(na, nb)
            chosen.append(x)
            dfs(k - 1, na // g, nb // g, x, chosen)
            chosen.pop()

    dfs(limit, a, b, 0, [])
    return best


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    a, b = next(data), next(data)
    g = gcd(a, b)
    a, b = a // g, b // g            # 先约分，搜索状态里保持最简分数
    for limit in range(1, 10):       # IDA*：加数个数从 1 开始逐层加深
        best = egypt_search(a, b, limit)
        if best is not None:
            print(*best)
            return


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 01:40
 * update_at: 2026-10-05 01:40
 */

#include <cstdio>

typedef long long ll;

// ===== IDA* 迭代加深搜索 埃及分数 =====
// 目标：把 a/b 拆成加数最少、其次最大分母最小、再字典序最小的单位分数和

ll ga, gb;      // 当前还差多少（最简分数）需要凑出
ll best[16];    // 目前全局最优的分母序列
ll path[16];    // 当前搜索路径上已选的分母
int depLimit;   // 本轮迭代加深允许的加数个数
bool hasBest = false; // 是否已经找到过可行解

// 计算最大公约数（辗转相除）
ll gcd_ll(ll a, ll b) {
    if (b == 0) return a;
    return gcd_ll(b, a % b);
}

// 比较两条分母序列谁更优：先比最大分母（小者优，即最小的分数更大），
// 再比整个序列的字典序（小者优）。返回 true 表示新序列比 best 更优
bool better() {
    // depLimit 相同时两条序列长度一致，最大分母就是最后一个元素
    if (path[depLimit] != best[depLimit]) return path[depLimit] < best[depLimit];
    for (int i = 1; i <= depLimit; i++) {
        if (path[i] != best[i]) return path[i] < best[i];
    }
    return false;
}

// 还剩 k 个加数要凑出 ga/gb，上一个已选分母是 last（初始为 0）
// dep 表示当前填到第几个位置
void dfs(int k, ll a, ll b, ll last, int dep) {
    // 边界：只剩最后一个加数，必须恰好 1/x = a/b，即 x = b/a
    if (k == 1) {
        if (b % a != 0) return;
        ll x = b / a;
        if (x <= last) return;      // 分母必须严格递增
        path[dep] = x;
        // 注意：最优性要等本层搜完才知道，同一层内始终保留目前最优的一条
        if (!hasBest || better()) {
            hasBest = true;
            for (int i = 1; i <= dep; i++) best[i] = path[i];
        }
        return;
    }

    // 下界：分母严格递增；且 1/x < a/b 才不会立刻超额，即 x > b/a
    ll lo = last + 1;
    if (b / a + 1 > lo) lo = b / a + 1;
    // 上界：剩下 k 项每个都 <= 1/x，所以必须有 k/x >= a/b，即 x <= k*b/a
    ll hi = k * b / a;

    for (ll x = lo; x <= hi; x++) {
        // a/b - 1/x = (a*x - b) / (b*x)，约分后进入下一层
        ll na = a * x - b;
        ll nb = b * x;
        ll g = gcd_ll(na, nb);
        path[dep] = x;
        dfs(k - 1, na / g, nb / g, x, dep + 1);
    }
}

int main() {
    ll a, b;
    scanf("%lld %lld", &a, &b);
    ll g = gcd_ll(a, b); // 先约分，保证搜索状态里是最简分数
    a /= g;
    b /= g;

    // IDA*：加数个数从 1 开始逐层加深，第一个搜出解的深度即最少项数
    for (depLimit = 1; depLimit <= 10; depLimit++) {
        // 重新初始化全局最优记录
        hasBest = false;
        dfs(depLimit, a, b, 0, 1);
        if (hasBest) {
            // 输出最优解：按升序输出各分母（与题解 main.py 一致，只输出分母序列一行）
            for (int i = 1; i <= depLimit; i++) {
                printf("%lld%c", best[i], i == depLimit ? '\n' : ' ');
            }
            break;
        }
    }
    return 0;
}

复杂度

时间复杂度：在深度上限为 $d$ （本题中 $d \le 8$ ）的迭代加深搜索中，上下界剪枝将每一步分支严格夹在 $[ \lfloor \frac{b}{a} \rfloor + 1, \lfloor \frac{k \cdot b}{a} \rfloor ]$ 内，极大缩减了搜索树节点数。在 $a, b < 1000$ 的数据范围内，搜索耗时远小于 1000ms（实际运行耗时几十毫秒至数百毫秒）。
空间复杂度： $O(d)$ ，递归深度与保存当前分母序列的空间均受深度上限 $d$ 约束，空间开销微乎其微。

总结

埃及分数问题是 IDA* 与数学不等式剪枝的典范应用：

利用题目的“项数最少”目标，把 BFS 的逐层扩展优势与 DFS 的极低空间消耗通过 IDA* 结合起来；
利用分母递增的特性，通过 $\frac{1}{x} < \frac{a}{b}$ 和 $\frac{k}{x} \ge \frac{a}{b}$ 确定严格的取值区间 $[lo, hi]$ ，将看似无穷的搜索空间压缩到极小范围。

图示解析

graph TD
    A["输入: a/b (已约分)"] --> B["IDA*: 限制项数 limit = 1, 2, 3..."]
    B --> C["回溯 DFS(k, a, b, last)"]
    C --> D{"k == 1 ?"}
    D -- 是 --> E["检查 b % a == 0 且 b/a > last"]
    E -- 满足 --> F["记录/更新本层最优解 (min 最大分母)"]
    D -- 否 --> G["计算上下界: lo = max(last+1, b//a+1), hi = k*b//a"]
    G --> H["枚举分母 x ∈ [lo, hi]"]
    H --> I["剩余分数 a'/b' = a/b - 1/x，递归 k-1"]
    I --> C
    F --> J{"本层是否搜出解?"}
    J -- 是 --> K["输出最优解，结束"]
    J -- 否 --> B

「一本通 1.3 练习 1」埃及分数

目录

形式化题目

正解

思路

1. 为什么采用 IDA*？

2. 搜索分支上下界推导与剪枝

代码

复杂度

总结

图示解析