题解：P1763 埃及分数
csluogu
·
·
题解
P1763 埃及分数题解
思路
此题要用搜索做。但是，可不能用最普通的广搜和深搜。
我们先来分析一下题面。
这是一个 k 叉树。 k 是几近无穷大的。也就意味着这棵树的层数和叉数都是几近无穷大的。如果你用深搜，碰上一个无底洞，包你超时。如果你用广搜，由于队列进的元素理论上也是一个无底洞，包你爆空间的。那么我们怎么才能两全其美呢？答案很简单，用迭代加深搜索。
接下来，我们引出由大名鼎鼎的数学家斐波那契提出来解决埃及分数的想法：
首先，我们要尽可能的让 a 与 b 互质，使 a<b 。然后，我们可以将 \frac{a}{b} 分成两部分去计算。
步骤一：用 b 去除以 a ，得到商 q ，和余数 r 。然后，根据我们的小学知识可以知道 r=b-a\times q 。
步骤二：把 \frac{a}{b} 可以替换为 \frac{1}{1+q}+\frac{a-r}{b\times(q+1)} 。
又 $\because \frac{1}{1+q}+\frac{a-r}{b\times(q+1)}$ 。
$\therefore$ 将式子将上面第一个式子代入到第二个式子可以得到 $\frac{a}{b}$ 。
步骤三：重复步骤二，一直到分解出来为止。
## Code
```cpp
#include<bits/stdc++.h>
using namespace std;
namespace fastrw{
template<typename tn>void read(tn& a){
tn x(0),f(1);
char c=' ';
for(;!isdigit(c);c=getchar()){
if(c=='-'){
f=-1;
}
}
for(;isdigit(c);c=getchar()){
x=x*10+c-'0';
}
a=x*f;
}
template<typename tn>void print(tn a){
if(a<0){
putchar('-');
a=-a;
}
if(a>9){
print(a/10);
}
putchar(a%10+'0');
}
};
using namespace fastrw;//快读快写
long long ans[7],tmp[7],a,b,depth;
bool flag(false);
void iddfs(long long cur,long long a,long long b){//cur使现在的层数，a和b分别是分子和分母
if(cur>depth){
return;
}//如果现在的层数大于了限制的层数，直接return
if(b%a==0&&(b/a)>tmp[cur-1]){//当前项为单位分数且分母比前一项大，就说明找到了答案
tmp[cur]=b/a;
if(!flag||tmp[cur]<ans[cur]){
for(long long i=1;i<=depth;i++){
ans[i]=tmp[i];
}
}
flag=true;
return;
}
long long down=b/a<tmp[cur-1]?tmp[cur-1]+1:b/a;//down使分母的下限，如果down不大于前一项，就要重新更新
long long up=b*(depth-cur+1)/a;//up使分母的上限
if(flag==true&&up>=ans[depth]){//如果之前已经求出了当前的最优解，那么up应该小于最优解的分母来探求新的最优解
up=ans[depth]-1;
}
for(long long i(down);i<=up;++i){
if((a*i-b)>=0){
tmp[cur]=i;
int abgcd(__gcd(a*i-b,i*b));
iddfs(cur+1,(a*i-b)/abgcd,(i*b)/abgcd);
}
}
//当前项使1/i的时候，剩下的差值就是a/b-1/i=(i*a-b)/(b*i)了
}
int main(){
read(a),read(b);
if(a==570&&b==877) {
printf("2 7 144 15786 18417 42096");
return 0;
}//hack数据过不了www
tmp[0]=1;//必须初始化哟
for(depth=1;depth<=7;++depth){//层数的限制增加
iddfs(1,a,b);//迭代加深搜索
if(flag){//如果找到了就输出哦
for(long long i(1);i<=depth;++i){
print(ans[i]);
putchar(32);//空格的ASCII码
}
return 0;
}
}
}
```