【题目】

题目描述：

任何一个分数都能才成若干个单位分数（形如 $1/a$ 的，$a$ 是自然数）的和。

对于一个分数 $a/b$，表示方法有很多种，但是哪种最好呢？

首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越好，如果还是相同，那么第二小的分数越大越好，依次类推下去。

例如对于 $19/45$，下列方法都是合法的

19/45=1/3 + 1/12 + 1/180 19/45=1/3 + 1/15 + 1/45 19/45=1/3 + 1/18 + 1/30 19/45=1/4 + 1/6 + 1/180 19/45=1/5 + 1/6 + 1/18

但是最好的是最后一种，因为 $1/18$ 比 $1/180$，$1/45$，$1/30$，$1/180$ 都大。

现在给出 $a,b(0<a<b<1000)$，求最好的表达方式。

输入格式：

输入一行，用两个整数表示 $a$，$b$

输出格式：

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

样例数据：

输入 19 45

样例输出 5 6 18

【分析】

一道迭代加深的题

依旧是不断增加 $dfs$ 的深度，对于每个深度都判断能否找到答案，能就输出，不然就继续 $dfs$

这里解释一些代码中的细节吧

对于一个分数 $a/b$，使得 $1/c\le a/b$ 的最小的 $c$ 是 $b/a+1$，所以要从 $b/a+1$ 开始枚举代码中的剪枝就是如果枚举到 $i$，后面的分数肯定都小于 $1/i$，如果 $(h-dep+1)/i\le a/b$，就肯定不行，直接 $break$

【代码】

#include<cstdio> #include<cstring> #include<algorithm> #define N 10005 #define ll long long using namespace std; int h; ll ans[N],temp[N]; bool better() { for(int i=h;i>=0;--i) if(ans[i]!=temp[i]) return ans[i]==-1||ans[i]>temp[i]; return false; } bool dfs(int dep,int start,ll a,ll b) { if(dep==h) { if(b%a) return false; temp[dep]=b/a; if(better()) memcpy(ans,temp,sizeof(ans)); return true; } bool flag=false; start=max((ll)start,b/a+1); for(int i=start;;++i) { if(b*(h-dep+1)<=a*i) break; temp[dep]=i; ll x=a*i-b,y=b*i,gcd=__gcd(x,y); if(dfs(dep+1,i+1,x/gcd,y/gcd)) flag=true; } return flag; } int main() { int a,b,i; scanf("%d%d",&a,&b); for(h=1;;++h) { memset(ans,-1,sizeof(ans)); if(dfs(0,b/a+1,a,b)) break; } for(i=0;i<=h;++i) printf("%lld ",ans[i]); return 0; }