感谢所有AC

传送门

思路

      在不清楚 a/b 可以分解多少个分数时，搜索树的深度是未知的，分母可以是无穷大，所以需要对搜索树的深度进行一定的限制来进行搜索。

      迭代加深搜索就是这样的一种搜索，在DFS上加上深度参数来限制搜索的深度，当深度超过限制后直接返回，不再向下搜索。

      在主体函数中循环深度，对各深度 dfs 直到找到答案推出循环。注意数据开 long long，搜索过程中保存路径。

代码

#include
using namespace std;
typedef long long ll;
ll ans[20], res[20];
int a, b, dep;
bool flag;
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
void dfs(ll a, ll b, int d) {
	if (d > dep)return;
	if (a == 1 && b > res[d - 1]) {
		res[d] = b;
		if (!flag || res[d] < ans[d])
			for (int i = 1; i <= dep; i++)
				ans[i] = res[i];
		flag = 1;
		return;
	}
	ll l = max(b / a + 1, res[d - 1] + 1);
	ll r = b * (dep - d + 1) / a;
	if (r >= ans[dep] && flag)
		r = ans[dep] - 1;
    //枚举的上下限的最优性剪枝
	for (ll i = l; i < r; i++)
		if (i > res[d - 1]) {
			res[d] = i;
			ll g = gcd(a * i - b, b * i);
			dfs((a * i - b) / g, b * i / g, d + 1);
		}
}
int main(void)
{
	ios::sync_with_stdio(false);
	cin >> a >> b;
	int c = gcd(a, b);
	a /= c, b /= c;
	for (dep = 1; dep <= 10; dep++)//迭代加深
	{
		dfs(a, b, 1);
		if (flag) {
			for (int i = 1; i <= dep; i++)
				cout << ans[i] << " ";
			break;
		}
	}
	return 0;
}