@CIHg2代码如下 已经写好了注释埃及分数题目

#include<iostream>
using namespace std;
typedef long long ll;
ll  a,b; ll dep; ll found=0;
ll now[1005];ll ans[1005];
int yuefen(ll aa, ll bb)
{
	if(bb==0)return aa;
	return yuefen(bb,aa%bb);	
}//这是一个约分的函数 
void Idfs(ll a,ll b,ll d)
{
	if(d==dep)
	{	//当进行自定的最后的深度 进行判断要求a此时必须为1了就是分子 
		//不能是2 3 4这些 这样说明没拆干净要继续拆的  now数组是指此时存贮的分母 ans是答案的
		if(a==1&&now[d-1]<b)
		{
			
			now[d]=b;
			if(!found||ans[d]>now[d])//没找到或者有更优解
			{
				for(int i=1;i<=dep;i++)ans[i]=now[i];//覆盖ans		
			}
			found=1;
		}
		return ;
	}
	ll left1=max(b/a+1,now[d-1]+1);
	ll right1=1e7;
	if(found)right1=ans[dep]-1;//如果找到了就可以进一步剪枝
	right1=min(right1,b/a*(dep-d+1));
	for(ll i=left1;i<=right1;i++)
	{ 	now[d]=i;
		ll shang=a*i-b;//通分 
		ll xia=b*i;//通分
		//自己少了 now[d]=i;
		int  g= yuefen(shang,xia);
		Idfs(shang/g,xia/g,d+1);		
	}	
}
int main()
{
	cin>>a>>b;
	for(dep=1;!found;dep++)	Idfs(a,b,1);
	for(int i=1;i<=dep-1;i++)cout<<ans[i]<<" ";	
	return 0;	
}