洛谷题面

题目大意

在古埃及，人们使用单位分数的和（形如 /(/dfrac{1}{a}/) 的，/(a/) 是自然数）表示一切有理数。如：/(/dfrac{2}{3} = /dfrac{1}{2} + /dfrac{1}{6}/)，但不允许 /(/dfrac{2}{3} = /dfrac{1}{3} + /dfrac{1}{3}/)，因为加数中有相同的。对于一个分数 /(/dfrac{a}{b}/)，表示方法有很多种，但是哪种最好呢？首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越好。如：

/[/begin{aligned}
/frac{19}{45} = /frac{1}{3} + /frac{1}{12} + /frac{1}{180}//
/frac{19}{45} = /frac{1}{3} + /frac{1}{15} + /frac{1}{45}//
/frac{19}{45} = /frac{1}{3} + /frac{1}{18} + /frac{1}{30}//
/frac{19}{45} = /frac{1}{4} + /frac{1}{6} + /frac{1}{180}//
/frac{19}{45} = /frac{1}{5} + /frac{1}{6} + /frac{1}{18}//
/end{aligned}
/]

最好的是最后一种，因为 /(/dfrac{1}{18}/) 比 /(/dfrac{1}{180}, /dfrac{1}{45}, /dfrac{1}{30}/) 都大。
注意，可能有多个最优解。如：

/[/begin{aligned}
/frac{59}{211} = /frac{1}{4} + /frac{1}{36} + /frac{1}{633} + /frac{1}{3798}//
/frac{59}{211} = /frac{1}{6} + /frac{1}{9} + /frac{1}{633} + /frac{1}{3798}//
/end{aligned}
/]

由于方法一与方法二中，最小的分数相同，因此二者均是最优解。

给出 /(a,b/)，编程计算最好的表达方式。保证最优解满足：最小的分数 /(/ge /dfrac{1}{10^7}/)。

题目分析

这道题的搜索树理论上是无限的，所以很难用 /(/verb!dfs!/) 做，而 /(/verb!bfs!/) 耗费空间太大，此时需要迭代加深搜索。

既然 /(/verb!dfs!/) 会无限延伸导致深度失控，那么我们就从小到大枚举这个深度 /(depth/) 来限制每次搜索的深度上界。

然后我们还需要一个估价函数（于是变成了 /(/verb!ID~A*!/)），假设枚举到 /(step/) 层时的分数为 /(/dfrac{c}{d}/)，目标分数为 /(/dfrac{a}{b}/)，而小于 /(/dfrac{a}{b}-/dfrac{c}{d}/) 的最大的 埃及分数 为 /(/dfrac{1}{e}/)，故还至少需要 /(/Delta=/dfrac{/dfrac{a}{b}-/dfrac{c}{d}}{/dfrac{1}{e}}/) 层搜索才能达到 /(/dfrac{a}{b}/)。我们可以直接判断 /(step+/Delta/) 是否不超过 /(depth/) 来完成极速剪枝。

具体的：

• 用一个函数 get_first(a,b) 来找到满足 /(/dfrac{1}{e}/lt /dfrac{a}{b}/) 最小的 /(e/)。可以推出 /(1/lt /dfrac{a}{b}/times e/) 亦即 /(e/gt /dfrac{b}{a}/)，又因为 /(e/) 是一个整数，所以 /(e/) 取 /(/dfrac{b}{a}+1/)。

• /(/verb!dfs!/) 过程中，/(now/) 表示当前可选择的最小分母，要注意 /(now/) 保证当前枚举的分母大于上一层的分母，get_first(a,b) 保证 /(/dfrac{1}{e}/lt/dfrac{a}{b}/)，两个条件均需满足，故两个取最大。

• 除法会产生精度误差，应多用乘法。枚举下一个分母 /(i/) 时，若后面接下来 /(depth-step+1/) 层全是 /(/dfrac{1}{i}/) 也不能达到 /(/dfrac{a}{b}/) 那么直接剪枝。/(/dfrac{1}{i}/times (depth-step+1)/le /dfrac{a}{b}/to b/times (depth-step+1)/le a/times i/)。

• 如果当前走到限制了，那么判断当前分数 /(/dfrac{a}{b}/) 是不是埃及分数，如果 /(b/) 不是是 /(a/) 的倍数或 /(b/) 超过了 /(10^7/) 则不是，否则判断是否更优，更优则输出。

代码

// Problem: P1763 埃及分数
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1763
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// Date:2022-06-27 22:54
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <cstdio>
#include <climits>//need "INT_MAX","INT_MIN"
#include <cstring>//need "memset"
#include <numeric>
#include <algorithm>
#include <cmath>
#define int long long
#define enter putchar(10)
#define debug(c,que) std::cerr << #c << " = " << c << que
#define cek(c) puts(c)
#define blow(arr,st,ed,w) for(register int i = (st);i <= (ed); ++ i) std::cout << arr[i] << w;
#define speed_up() std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0)
#define mst(a,k) memset(a,k,sizeof(a))
#define stop return(0)
const int mod = 1e9 + 7;
inline int MOD(int x) {
	if(x < 0) x += mod;
	return x % mod;
}
namespace Newstd {
	char buf[1 << 21],*p1 = buf,*p2 = buf;
	inline int getc() {
		return p1 == p2 && (p2 = (p1 = buf) + fread(buf,1,1 << 21,stdin),p1 == p2) ? EOF : *p1 ++;
	}
	#ifndef ONLINE_JUDGE
	#define getc getchar
	#endif
	inline int read() {
		int ret = 0,f = 0;char ch = getc();
		while (!isdigit(ch)) {
			if(ch == '-') f = 1;
			ch = getc();
		}
		while (isdigit(ch)) {
			ret = (ret << 3) + (ret << 1) + ch - 48;
			ch = getc();
		}
		return f ? -ret : ret;
	}
	inline double double_read() {
		long long ret = 0,w = 1,aft = 0,dot = 0,num = 0;
		char ch = getc();
		while (!isdigit(ch)) {
			if (ch == '-') w = -1;
			ch = getc();
		}
		while (isdigit(ch) || ch == '.') {
			if (ch == '.') {
				dot = 1;
			} else if (dot == 0) {
				ret = (ret << 3) + (ret << 1) + ch - 48;
			} else {
				aft = (aft << 3) + (aft << 1) + ch - '0';
				num ++;
			}
			ch = getc();
		}
		return (pow(0.1,num) * aft + ret) * w;
	}
	inline void write(int x) {
		if(x < 0) {
			putchar('-');
			x = -x;
		}
		if(x > 9) write(x / 10);
		putchar(x % 10 + '0');
	}
}
using namespace Newstd;

const int N = 1e5 + 5;
int t[N],ans[N];
int a,b,depth;
inline int gcd(int a,int b) {
	return b == 0 ? a : gcd(b,a % b);
}
//找到满足 1 / c < a / b 最小的 c
inline int get_first(int a,int b) {
	return b / a + 1;
}
inline bool check(int step) {
	if (!ans[step]) return true;
	return t[step] < ans[step];
}
//now:当前可选择的最小分母
inline bool dfs(int step,int now,int a,int b) {
	if (step == depth) {
		if (b % a != 0 || b > 1e7) return false;
		t[step] = b / a;
		if (t[step] <= t[step - 1]) return false;
		if (check(step)) memcpy(ans,t,sizeof(ans));
		return true;
	}
	bool mark = false;
	now = std::max(now,get_first(a,b));
	for (register int i = now;; ++ i) {
		if (b * (depth - step + 1) <= i * a) break;
		t[step] = i;
		int a1 = a * i - b,b1 = b * i;
		int t = gcd(a1,b1);
		a1 /= t,b1 /= t;
		if (dfs(step + 1,now + 1,a1,b1)) mark = true;
	}
	return mark;
}
int32_t main(void) {
	a = read(),b = read();
	int t = gcd(a,b);
	a /= t,b /= t;
	for (depth = 1;; ++ depth) {
		if (dfs(0,get_first(a,b),a,b)) {
			break;
		}
	}
	for (register int i = 0;i <= depth; ++ i) printf("%lld ",ans[i]);
	
	return 0;
}