这里是（过了洛谷hack数据的）完整版代码。这种题目不自己亲手认真调试，很多细节是真的无法通过语言描述的。

相比我前一条题解，大的修改有两处：

1. 增加了“通过解方程来求最后两个分数”的剪枝；
2. 应上一条修改的要求，给最后一个分母的上限做了迭代加深。因为要枚分数 a/b 的GCD，而这个值的上限基本接近 int(1e7)，不做迭代加深的话很慢。

补充两点说明：

• 此处我不再推荐任何一个题解了，因为我认真读了很多题解，发现都有一些数学推导过程中的小笔误，或者马蜂奇怪，大家自己综合阅读多个题解，然后采众家之长吧，同时锻炼自己发现笔误的能力，可以迁移到你“考试的时候检查自己试卷错误”的情境。
• 在DFS的第二个 if 语句处，我原本的写法是 if(x==dep) {if(a==1) ...}，语义是“要求递归到最大深度时恰好出现正解”，第一个数据点是35ms，hack数据点T；现在我改成 if(a==1) {...} 并且在前面加了递归边界 if(x>dep) return false;，第一个数据点5ms，hack数据点过了。请大家认真体会，你的代码也会出现这样恼人但又发人深省的小细节，所以请一定要认真亲手写代码，动脑动手调试直至AC！！！

完整代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// a/b向上取整
inline ll ceil(int a, int b) {
	return (a + b - 1) / b;
}

const int N = 50;
ll ans[N], tmp[N];
int dep = 1; // 当前搜索深度，需要对这个变量进行迭代加深
ll maxb = 1e3; // 最后一个分母的上界，
// “解方程求最后两个分数”的做法需要对它迭代加深，因为k的上界太大

// 现在还剩余的数是a / b，选到第x个数
bool dfs(ll a, ll b, int x) {
	if (x > dep) return false;
	// 当前分数如果分子为1，那就一定是一个备选答案
	if (a == 1) {
		// 最后一个分数的分母一定要比前一个大
		if (b > tmp[x - 1]) {
			// 假如没找到过这个长度的答案，
			// 或最后一个分母比之前的答案小
			if (!ans[x] || b < ans[x]) {
				tmp[x] = b;
				memcpy(ans, tmp, sizeof tmp);
			}
		}
		return true;
	}

	// 只剩下两个分数时，直接解方程求解，不要枚举了。
	// x+y=ak, xy=bk (k>=2) 联立方程组，用x替代y，
	// 得到一元二次方程 x^2-akx+bk=0，
	// 判别式为 a^2 * k^2-4bk，由于x和y不同所以判别式大于0
	if (x == dep - 1) {
		ll l = (b << 2) / a / a + ((b << 2) % (a * a) != 0);
		ll r = min((maxb << 1) / a, maxb * (maxb - 1) / b);
		for (int k = l; k <= r; k++) {
			// 判别式要大于0
			ll delta = a * a *	k * k - (b << 2) * k;
			// 主要是排除delta==0的情况
			if (delta <= 0) continue;
			ll d = sqrt(delta);
			// 如果delta不是完全平方数，或求根公式的分子不能被分母整除
			if (d * d != delta || (a * k + d) & 1) continue;
			// x1、x2是方程的两个根
			ll x1 = (a * k - d) >> 1;
			// 解出来的值（分母）可能小于等于前一个
			if (x1 <= tmp[dep - 2]) continue;
			ll x2 = (a * k + d) >> 1;
			// 此情况下的最后一个分数是 ans[dep]！！！
			if (!ans[dep] || x2 < ans[dep]) {
				tmp[dep - 1] = x1, tmp[dep] = x2;
				memcpy(ans, tmp, sizeof tmp);
				return true;
			}
		}
		// 注意这里一定要return，因为这个分支往后做已经找不到答案了
		return false;
	}
	// 枚举分母，上下界见题解的优化2
	ll l = max(ceil(b, a), tmp[x - 1] + 1);
	ll r = min((dep - x + 1) * b / a, maxb);
	bool flag = false;
	for (int i = l; i <= r; i++) {
		tmp[x] = i;
		// 通分减去 1/i 后，分子分母分别是 a*1-b, b*i
		ll g = __gcd(a * i - b, b * i);
		// 递归到下一层（找下一个分数）
		flag |= dfs((a * i - b) / g, b * i / g, x + 1);
	}

	return flag;
}

int main() {
	int A, B;
	cin >> A >> B;
	int g = __gcd(A, B);
	A /= g, B /= g; // 约分

	tmp[0] = 1;
	// 100层很深了，不可能达到，基本约等于 while(1) 了。
	while (dep < 100) {
		// 先在同一层对最后一个分母进行迭代加深
		for (maxb = 1e4; maxb <= 1e7; maxb *= 10) {
			if (dfs(A, B, 1)) {
				for (int i = 1; i <= dep; i++) cout << ans[i] << " ";
				return 0;
			}
		}
		// 然后对深度迭代加深
		++dep;
	}

	return 0;
}

没有加入最后一个剪枝（最后两个分数通过解方程来算得）的版本。

其中有一个非常重要的需要注意的地方，在DFS函数枚举分母那个循环的最后一句应为：

flag |= dfs((a * i - b) / g, b * i / g, x + 1);

• 第一，当该dfs函数返回true时，不能直接结束循环返回上一层，即不能写成：

if(dfs((a * i - b) / g, b * i / g, x + 1)) return true;

因为第i个分母都是从小到大枚举的，当搜到可行分解时，若此处直接返回，那么就不会继续往后搜索最后一个分母最小的正解了。比如样例 19 45 会得到错误输出 3 12 180，原因就是找到第一个可行分解后就不再往后搜了。

• 第二，不要nc写成

flag = dfs((a * i - b) / g, b * i / g, x + 1);

否则你搜索的最后一个分支如果返回false那就糟了（即使前面搜到了答案，你程序的返回值含义也是“未搜到”）。

当然，如果你dfs函数返回void，那就是另一个写法了。

推荐题解：

最后一个解方程优化，请参考洛谷题解，例如：

如果以上题解你看不懂，就换其他的看，结合不同的题解，你一定能弄懂。

完整（未能过洛谷hack）的代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// a/b向上取整
inline ll ceil(int a, int b) {
	return (a + b - 1) / b;
}

const int N = 50;
ll ans[N], tmp[N];
int dep = 1;

// 现在还剩余的数是a / b，选到第x个数
bool dfs(ll a, ll b, int x) {
	if (x == dep) {
		// 最后一个分数必须满足分子是1 && 分母比前一个大
		if (a == 1 && b > tmp[x - 1]) {
			// 假如没找到过这个长度的答案，
			// 或最后一个分母比之前的答案小
			if (!ans[x] || b < ans[x]) {
				tmp[x] = b;
				memcpy(ans, tmp, sizeof tmp);
				return true;
			}
		}
		return false;
	}
	// 枚举分母，上下界见题解的优化2
  // 这里也要注意！！！上界是 b/a 向上取整！
	ll l = max(ceil(b, a), tmp[x - 1] + 1);
	ll r = min((dep - x + 1) * b / a, 10000000LL);
	bool flag = false;
	for (int i = l; i <= r; i++) {
		tmp[x] = i;
		// 通分减去 1/i 后，分子分母分别是 a*1-b, b*i
		ll g = __gcd(a * i - b, b * i);
		// 递归到下一层（找下一个分数）
		flag |= dfs((a * i - b) / g, b * i / g, x + 1);
	}

	return flag;
}

int main() {
	int A, B;
	cin >> A >> B;
	int g = __gcd(A, B);
	A /= g, B /= g; // 约分

	tmp[0] = 1;
	while (!dfs(A, B, 1)) ++dep;

	for (int i = 1; i <= dep; i++) cout << ans[i] << " ";

	return 0;
}