题目描述 Description
在古埃及，人们使用单位分数的和(形如1/a的, a是自然数)表示一切有理数。 如：2/3=1/2+1/6,但不允许2/3=1/3+1/3,因为加数中有相同的。 对于一个分数a/b,表示方法有很多种，但是哪种最好呢？ 首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越 好。 如： 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),编程计算最好的表达方式。
输入描述 Input Description
a b
输出描述 Output Description
若干个数，自小到大排列，依次是单位分数的分母。
样例输入 Sample Input
19 45
样例输出 Sample Output
5 6 18
/* 感觉自己写的和正解完全不一样，我是枚举的答案的最小公倍数，无情的WA了，原因是数据太大，最小公倍数太大。 正解是迭代加深直接搜答案，但是左右边界边界确定的特别巧妙。 */ #include<cstdio> #include<iostream> #include<algorithm> #define N 1010 #define ll long long using namespace std; ll n,m,flag,ans[N],q[N]; ll Ceil(double x) { return (ll)(x+0.999999); } ll gcd(ll a,ll b) { if(!b)return a; return gcd(b,a%b); } void dfs(ll a,ll b,ll t,ll limit) { ll c=gcd(a,b);a/=c;b/=c; if(t==limit) { if(a==0&&(!flag||(flag&&q[t-1]<ans[t-1]))) { for(ll i=0;i<limit;i++) ans[i]=q[i]; flag=1; } return; } ll l=Ceil(double(b)/double(a));//左边界 ll r=Ceil((double(limit)-double(t))/(double(a)/double(b)));//右边界 for(ll i=max(l,q[t-1]+1);i<=r;i++) { if(flag&&i>ans[limit-1])return; q[t]=i;dfs(a*i-b,b*i,t+1,limit);q[t]=0; } } int main() { cin>>n>>m; for(ll i=1;i<=20;i++) { dfs(n,m,0,i); if(flag) { for(ll j=0;j<i;j++)cout<<ans[j]<<" "; break; } } return 0; }