埃及分数

一本通·提高篇 · 代码 · cpp · 难度 5/5 · 共 1775 字
迭代加深 DFS 枚举分母，比最大分母取优
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1444
// 题意：把分数 a / b 表示成若干个互不相同的单位分数之和，要求项数最少，项数相同时让最小的那个分数尽量大（即最大分母尽量小），输出各分母。
// 思路：迭代加深 DFS，深度即项数。
// 1. 每层的分母严格递增，枚举下界由 1 / x <= 剩余值 与 x >= 上一个分母 + 1 共同决定。
// 2. 上界剪枝：剩下的 dep 项每项都不超过 1 / x，若 dep / x 仍小于剩余值则停止增大 x。
// 3. 固定深度内枚举全部解，比较时从最大分母开始比，越小越优。
// 复杂度：指数级搜索，深度较小时很快出解
// 易错点：分母必须互不相同，递归时下界是 x + 1 而不是 x。
// 易错点：中间分数会不断通分放大，long long 也可能溢出，乘法前先判断是否超过 LLONG_MAX / b。
#include <bits/stdc++.h>
using namespace std;
long long A, B;
int maxd;
long long cur[64], best[64];
bool hasBest = false;
void update(){
    if(!hasBest){
        for(int i = 0; i < maxd; i++) best[i] = cur[i];
        hasBest = true;
        return;
    }
    for(int i = maxd - 1; i >= 0; i--){
        if(cur[i] != best[i]){
            if(cur[i] < best[i]){
                for(int k = 0; k < maxd; k++) best[k] = cur[k];
            }
            return;
        }
    }
}
void dfs(int dep, long long a, long long b, long long start){
    if(dep == 1){
        if(b % a) return;
        long long x = b / a;
        if(x < start) return;
        cur[maxd - 1] = x;
        update();
        return;
    }
    for(long long x = start; ; x++){
        if((__int128)a * x > (__int128)b * dep) break;
        if(x > LLONG_MAX / b) break;
        long long na = a * x - b;
        if(na <= 0) continue;
        long long nb = b * x;
        long long g = std::gcd(na, nb);
        na /= g;
        nb /= g;
        cur[maxd - dep] = x;
        dfs(dep - 1, na, nb, x + 1);
    }
}
int main(){
    if(!(cin >> A >> B)) return 0;
    for(maxd = 1; ; maxd++){
        hasBest = false;
        dfs(maxd, A, B, 1);
        if(hasBest) break;
    }
    for(int i = 0; i < maxd; i++){
        if(i) cout << " ";
        cout << best[i];
    }
    cout << "\n";
    return 0;
}
埃及分数

正文

一本通·提高篇的其它内容
