老师的满分代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b;
vector<int>tmp,ans;//存放分母值
ll gcd(ll a,ll b)//最大公约数
{
	return b==0?a:gcd(b,a%b);
}
// a/b表示当前的分数，depth表示当前深度，start表示下一个加数的分母的起始值，maxb表示分母的最大值，maxdepth表示最大深度
void dfs(ll a,ll b,int depth,ll start,int maxb,int maxdepth)
{
	if(depth>maxdepth) return;//剪枝，如果当前深度大于最大深度，那么就不用继续搜索了
	ll d=gcd(a,b);
	a/=d,b/=d;//将a和b约分
	if(b>maxb) return;//剪枝，如果b大于最大分母，那么就不用继续搜索了
	if(a==1&&b>tmp.back())//最后一个加数的分母必须是最大的
	{
		tmp.push_back(b);
		if(ans.size()==0 || (tmp.size()==ans.size() && tmp.back()<ans.back())) ans=tmp;
		tmp.pop_back();
		return;
	}
	start=max(start,b/a+1);//剪枝，从b/a+1开始搜索，这样就可以避免重复搜索
	for(int i=start;;i++)//枚举下一个加数的分母
	{
		if(b*(maxdepth-depth+1)<a*i) break;//剪枝，如果当前深度到最大深度的剩余搜索空间都不够，那么就不用继续搜索了
		if(i>maxb) break;//剪枝，如果当前分母大于最大分母，那么就不用继续搜索了
		tmp.push_back(i);
		dfs(a*i-b,b*i,depth+1,i+1,maxb,maxdepth);
		tmp.pop_back();
	}
}
int main()
{
	cin>>a>>b;
	for(int maxdepth=1;maxdepth<=10;maxdepth++)//迭代加深最大深度 2^10=1024满足最大值1000
	{
		for(int maxb=1000;maxb<=1e7;maxb*=10)//迭代加深分母的最大值
		{
			dfs(a,b,1,1,maxb,maxdepth);
			if(ans.size())break;//如果找到解，那么就不用继续增加最大分母
		}
		if(ans.size()) break;//如果找到解，那么就不用继续增加最大深度
	}
	for(auto v:ans) cout<<v<<" ";
	return 0;
}

同学的85分代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b;
vector<int>tmp,ans;
ll gcd(ll a,ll b)
{
	return b==0?a:gcd(b,a%b);
}
void dfs(ll a,ll b,int dp,ll start,int maxb,int maxdp)
{
	if(dp>maxdp)return;
	ll d=gcd(a,b);
	a/=d,b/=d;
	if(b>maxb) return;
	if(a==1 && b>tmp.back())
	{
		tmp.push_back(b);
		if(ans.size()==0 || (tmp.size()==ans.size() && tmp.back()<ans.back())) ans=tmp;
		tmp.pop_back();
		return;
	}
	start=max(start,b/a+1);
	for(int i=start;;i++)
	{
		if(b*(maxdp-dp+1)<a*i)break;
		if(i>maxb)break;
		tmp.push_back(i);
		dfs(a*i-b,b*i,dp+1,i+1,maxb,maxdp);
		tmp.pop_back();
	}
}
int main()
{
	cin>>a>>b;
	for(int maxdp=1;maxdp<=10;maxdp++)
	{
		for(int maxb=1000;maxb<=1e7;maxb*=10)
		{
			dfs(a,b,1,1,maxb,maxdp);
			if(ans.size())break;
		}
		if(ans.size())break;
	}
	for(auto v:ans) cout<<v<<" ";
	return 0;
}