题解：P1763 埃及分数

__CrossBow_EXE__ · 2025-10-16 20:07:38 · 题解

前言

:::info[关于文章渲染] 本文章使用了 2025 年 7 月的新版 Markdown 进行渲染。 :::

非常好搜索，使我的大脑旋转。

:::info[前置知识]

• IDDFS，迭代加深搜索
• 搜索剪枝
• 韦达定理
• 一元二次方程的判别式、求根公式等
• 一些卡常小技巧 :::

题意

给出分数 \frac{a}{b}，我们想要将它拆成若干个埃及分数（分子为 1 的真分数）之和。要求：

• 真分数两两不同
• 拆出来的分数最少
• 其中最小的分数最大

求出一种拆分方案。

数据范围：1<a<b<10^3，且答案满足最小的分数大于等于 \frac{1}{10^7}。

100pts，hack TLE

首先有一个小结论：分数数量不超过 10 个。下面有一个感性证明。

:::info[感性证明] 对于一个分数，如果想让它拆出来的分数更多，分数就要大。因为是真分数，越大就越接近 1。这里以 \frac{a}{1000} 举例。

对于它，我们可以先拆成 a 个 \frac{1}{1000} 之和。接着，我们分别将 1,2,4,8,\dots 个 \frac{1}{1000} 合并，这样就把它分成了 \frac{1}{1000}+\frac{2}{1000}+\frac{4}{1000}+\dots。显然，根据倍增思想，大概只会拆出来 \log_2 b 个埃及分数，再加上剩余的最多 1 个，最多也只有 10 个分数。

得证。 :::

这么小，考虑搜索拆分的数。但关于用哪种搜索方式，有一个问题：

• 如果使用 dfs，可能会陷入一个错解出不来
• 如果使用 bfs，那样搜索树的深度最大为

这里隆重推荐 IDDFS，迭代加深搜索。它的思想是规定一个在搜索树上从下搜索的深度，如果超过深度直接停止搜索。你应该对它有所了解。在这道题中，深度等价于拆出的分数个数。

由于分数个数很少，我们可以记录下来我们分别选了哪些分数。显然，我们如果当前要凑出 \frac{a}{b}，就可以枚举所有小于它的埃及分数。我们可以缩小枚举的分母的上下界来优化。（详细讨论见下）

注意开 long long 和约分。

::::info[代码及详细讲解]

下面有一些为了表述方便而制定的规定。 :::info[规定]

• 搜索状态 dfs(a,b,x,dep)：需要凑出 \frac{a}{b}，当前搜索进行到了 x 层，最大为 dep 层。
• 一个解：一种满足条件的拆分方案

此外，后文中类似 \frac{a}{b} 的分子不为 1 的分数，如果没有特殊说明都表示 \frac{1}{\left \lfloor \frac{b}{a} \right \rfloor}。 :::

对当前的搜索情况分类讨论：（这一坨是重点，对于正解有很大帮助，建议配合代码理解）

• 如果 a=1，那么可能加上一个 \frac{1}{b} 就能得到最优解。这样，如果当前没有解，或者当前有了解，但是不如这个解更优，那么这是一个更优的解，就把 fm 数组赋值到 ans。

• 否则，需要枚举这一步拆分的分数分母。求出来这个分母的上下界，进行更深一层的搜索即可。下面是对上下界的讨论。

  • 对于下界 l，为了保证拆分方案的递减，应该从前一个拆分出来的分母 +1 开始。同时为了凑出来当前的 \frac{a}{b}，还要保证分母至少为 \left \lfloor \frac{b}{a} \right \rfloor。两个数取较大值即可。
  • 对于上界 r，如果当前剩余 \frac{a}{b}，显然在搜索树上，从当前节点到限定深度中间会经过 dep-x+1 个点（类比一条从当前节点往下垂的链），考虑极端情况，中间这条链全拆出了最大值 \frac{a}{b}（分母为 \left \lfloor \frac{b}{a} \right \rfloor），那么为了保证能拆出这么多分母，当前节点的分母就要取到 (dep-x+1)\times\left \lfloor \frac{b}{a} \right \rfloor。此外，如果发现已经有了解，那么根据最优性剪枝，搜索劣于目前最优解肯定对于找到最优解无用，所以直接从优于最优解的分母开始搜索即可。

那么，找到上下界后，就可以枚举这次拆分的分母继续搜索就行了。注意范围是 [l,r)，因为 r 是取不到的极端情况。

我真不知道怎么才能说得更详细了，还是看代码吧（逃

:::warning[警告]

• 代码中使用了 #define int long long
• 代码只给出了关键部分。 :::

:::info[代码] record

int a,b,g;
int fm[15],ans[15];
bool found=0;//有没有找到解
void dfs(int a,int b,int x,int dep){
    if(x>dep) return;//层数超过了dep还没有找到解，直接停止
    if(a==1&&b>fm[x-1]){//只剩1/b就能凑出答案 
        fm[x]=b;
        if(!found||b<ans[x]){//暂时没有解，或者最小分数1/b比之前的结果更大 
            up(i,1,x) ans[i]=fm[i];//复制答案 
            found=1;
            return;
        }
    } 
    int l=max(b/a,fm[x-1]+1);//分母下界
    int r=(dep-x+1)*b/a;//分母上界：假设儿子都是a/b，显然不可能 
    if(found) r=min(r,ans[dep]-1);//之前有过解，不用再搜索比之前的解更差的解，把上界调低
    up(i,l,r-1){//枚举放入的1/i，不可能达到r 
        fm[x]=i;//选择1/i 
        g=__gcd(a*i-b,b*i);
        dfs((a*i-b)/g,b*i/g,x+1,dep);//a/b-1/i=(a*i-b)/b*i
    } 
}
void Main(int cases){
    a=read(),b=read();g=__gcd(a,b);
    a/=g,b/=g;fm[0]=1;
    up(d,1,10){//枚举分数个数 
        dfs(a,b,1,d);//需要凑出a/b，当前在第一层（根），最多到第d层 
        if(found){
            up(i,1,d) cout<<ans[i]<<' ';
            return;
        }
    }
    return;
}

:::

::::

hack 全部超时，考虑剪枝。

第一个剪枝

我们发现搜索树的深度虽然被 IDDFS 限定了，但是宽度依旧很大。考虑同时限定搜索树的宽度，即限定最小的拆分出来的分数。

具体地，我们从搜索参数中加上一个 maxb，