[Vijos1308]埃及分数（迭代加深搜索 + 剪枝）

传送门

迭代加深搜索是必须的，先枚举加数个数

然后搜索分母

这里有一个强大的剪枝，就是确定分母的范围

#include <cstdio>

#include <cstring>

#define N 100001

#define LL long long

#define min(x, y) ((x) < (y) ? (x) : (y))

#define max(x, y) ((x) > (y) ? (x) : (y))

int n, flag, best = 9999999;

int ans[N], s[N] = {1};

inline void dfs(LL a, LL b, int k)

{

	LL i, x, y, l, r;

	if(!a)

	{

		flag = 1;

		best = s[n];

		for(i = 1; i <= n; i++)

			ans[i] = s[i];

		return;

	}

	if(k > n) return;

	l = max(s[k - 1] + 1, b / a);

	r = min(best - 1, b * (n - k + 1) / a);

	for(i = l; i <= r; i++)

		if(a * i >= b)

		{

			x = a * i - b;

			y = b * i;

			s[k] = i;

			dfs(x, y, k + 1);

		}

}

int main()

{

	int i;

	LL a, b;

	scanf("%lld %lld", &a, &b);

	while(!flag)

	{

		n++;

		dfs(a, b, 1);

	}

	for(i = 1; i <= n; i++)

		printf("%d ", ans[i]);

	return 0;

}