埃及分数
描述
任何一个分数都能才成若干个单位分数(形如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的深度 而对于这道题：
全局long long真好用
代码
#include<bits/stdc++.h>
#define re register
#define N 100000
#define int long long
using namespace std
;
int a
,b
,ans
[N
],tmp
[N
];
int get(int x
,int y
){return y
/x
+1;}
int gcd(int x
,int y
){
int z
=x
%y
;
while(z
){x
=y
;y
=z
;z
=x
%y
;}
return y
;
}
bool better(int len
){
for(int i
=len
;i
>=0;--i
)
if(ans
[i
]!=tmp
[i
])
return ans
[i
]==-1||tmp
[i
]<ans
[i
];
return false;
}
bool dfs(int limit
,int d
,int from
,int x
,int y
){
if(d
==limit
){
if(y
%x
) return false;
tmp
[d
]=y
/x
;
if(better(d
)) memcpy(ans
,tmp
,sizeof(tmp
));
return true;
}
int flag
=0;
from
=max(from
,get(x
,y
));
for(int i
=from
;;i
++){
if(1ll*y
*(limit
-d
+1)<=1ll*x
*i
) break;
int xx
,yy
;
tmp
[d
]=i
;
xx
=1ll*x
*i
-y
;
yy
=y
*i
;
int gd
=gcd(xx
,yy
);
if((dfs(limit
,d
+1,i
+1,xx
/gd
,yy
/gd
))) flag
=1;
}
return flag
;
}
signed main(){
cin
>>a
;cin
>>b
;
int sta
=get(a
,b
),i
,j
;
for(i
=1;;i
++){
memset(ans
,-1,sizeof(ans
));
if(dfs(i
,0,sta
,a
,b
)) break;
}
for(j
=0;j
<=i
;++j
) cout
<<ans
[j
]<<' ';
return 0;
}
