描述 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),编程计算最好的表达方式。
输入：a b
输出：若干个数，自小到大排列，依次是单位分数的分母。
样例输入 Sample Input
19 45
样例输出 Sample Output
5 6 18
时间限制 Time Limitation
各个测试点1s
来源 Source
from OIBH 信息学练习赛 #1 第三题
【参考程序】：
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
__int64 best[1010],ans[1010];
__int64 n,m;
int k,found=0;
int gcd(__int64 a,__int64 b)
{
__int64 t;
while (b)
{
t=a; a=b; b=t%b;
}
return a;
}
void dfs(__int64 x,__int64 y,int dep)
{
if (dep==k)
{
if (x==1 && y>0 && best[dep-1]<y)
{
best[dep]=y;
if (ans[dep]>best[dep])
{
for (int i=1;i<=dep;i++) ans[i]=best[i];
found=1;
}
if (dep==1 && found)
{
printf("%I64d\n",y);
exit(0);
}
}
return ;
}
if (dep>k) return ;
__int64 xx,yy,f,t,gg;
f=y/x+1; t=(k-dep+1)*y/x+1;
for (int i=f;i<=t;i++)
if (i>best[dep-1])
{
best[dep]=i;
xx=x*i-y; yy=y*i;
gg=gcd(xx,yy);
xx/=gg; yy/=gg;
dfs(xx,yy,dep+1);
}
if (found && dep==1)
{
for (int i=1;i<=k-1;i++) printf("%I64d ",ans[i]);
printf("%I64d\n",ans[k]);
exit(0);
}
}
int main()
{
scanf("%I64d%I64d",&n,&m);
__int64 g;
g=gcd(n,m);
n/=g; m/=g;
for (k=1;;k++)
{
memset(best,0,sizeof(best));
memset(ans,127,sizeof(ans));
dfs(n,m,1);
}
return 0;
}