~~I don't know how to do that fucking things.~~

埃及分数

题目描述

来源：BIO 1997 Round 1 Question 3

在古埃及，人们使用单位分数的和（形如 \(\dfrac{1}{a}\) 的，\(a\) 是自然数）表示一切有理数。如：\(\dfrac{2}{3} = \dfrac{1}{2} + \dfrac{1}{6}\)，但不允许 \(\dfrac{2}{3} = \dfrac{1}{3} + \dfrac{1}{3}\)，因为加数中有相同的。对于一个分数 \(\dfrac{a}{b}\)，表示方法有很多种，但是哪种最好呢？首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越好。如：

\[\begin{aligned} \frac{19}{45} &= \frac{1}{3} + \frac{1}{12} + \frac{1}{180}\\ \frac{19}{45} &= \frac{1}{3} + \frac{1}{15} + \frac{1}{45}\\ \frac{19}{45} &= \frac{1}{3} + \frac{1}{18} + \frac{1}{30}\\ \frac{19}{45} &= \frac{1}{4} + \frac{1}{6} + \frac{1}{180}\\ \frac{19}{45} &= \frac{1}{5} + \frac{1}{6} + \frac{1}{18}\\ \end{aligned} \]

最好的是最后一种，因为 \(\dfrac{1}{18}\) 比 \(\dfrac{1}{180}, \dfrac{1}{45}, \dfrac{1}{30}\) 都大。
注意，可能有多个最优解。如：

\[\begin{aligned} \frac{59}{211} &= \frac{1}{4} + \frac{1}{36} + \frac{1}{633} + \frac{1}{3798}\\ \frac{59}{211} &= \frac{1}{6} + \frac{1}{9} + \frac{1}{633} + \frac{1}{3798}\\ \end{aligned} \]

由于方法一与方法二中，最小的分数相同，因此二者均是最优解。

给出 \(a,b\)，编程计算最好的表达方式。保证最优解满足：最小的分数 \(\ge \cfrac{1}{10^7}\)。

输入格式

一行两个整数，分别为 \(a\) 和 \(b\) 的值。

输出格式

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

样例 #1

样例输入 #1

19 45

样例输出 #1

5 6 18

提示

\(1 \lt a \lt b \lt 1000\)

上代码（附解释）

/*
在古埃及，人们使用单位分数的和(形如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),编程计算最好的表达方式
 */
/*
in:
19 45
out:
5 6 18
*/
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iostream>
#define ll long long
#include <algorithm>
using namespace std;
#define endl "\n"
//depth:最多允许的层数，temp:边搜边存结果
//ans:存储最优解(擂主)
ll depth,temp[1001],ans[1001];
bool flag=0;
ll gcd(ll a,ll b) {
	return b==0?a:gcd(b,a%b);
}
//分子是a，分母是b 递归树层数step
void dfs(ll a,ll b,ll step) {
	if (step==depth) {
		if (a==1) { //最后一个分子是1
			temp[step]=b;
			//最后一个分母第一次赋值(搜索到第一个可行解)，或者比之前的分母小，更新答案
			if (ans[step]==0||temp[step]<ans[step]){
				flag=1;
				copy(temp,temp+depth+1,ans);
			}
		}
		//无论是否成立，都必须return，不然就超过递归树的层数
		return;
	}
	ll first=b%a!=0?b/a+1:b/a;
	//起始值要么是上一个数字+1，要么是ceil(b/a)
	int st=max(temp[step-1]+1,first);
	//终点是分母允许的最大值(考虑剩余层数)
	int ed=(b/a)*(depth-step+1);
//	if(depth==3&&a==19&&b==45){
//		cout<<"调试信息:";
//		cout<<st<<" "<<ed<<endl;
//	}
	for(ll i=st; i<=ed; i++) {
		temp[step]=i;
		ll nexta,nextb,g;
		//分数的减法，nextb为通分的值
		//a/b - 1/i
		//a*i/b*i - b/b*i
		nexta=a*i-b,nextb=b*i;
		g=gcd(nexta,nextb);//求gcd便于约分
		dfs(nexta/g,nextb/g,step+1);
	}
}

int main() {
	ll a,b;
	cin>>a>>b;
	ll g=gcd(a,b);
	temp[0]=1;
	for(depth=1;depth<=b; depth++) {
		memset(ans,0,sizeof(ans));
		dfs(a/g,b/g,1);
		if (flag) break;
	}
	for(int i=1; i<=depth; i++)
		printf("%lld ",ans[i]);
	return 0;
}