专栏文章

题解：P1763 埃及分数

___CrossBow_EXE__
P1763题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minla3s0
此快照首次捕获于
2025/12/02 04:15
3 个月前
此快照最后确认于
2025/12/02 04:15
3 个月前
查看原文

前言

关于文章渲染
本文章使用了 2025 年 7 月的新版 Markdown 进行渲染。
非常好搜索，使我的大脑旋转。
前置知识
  • IDDFS，迭代加深搜索
  • 搜索剪枝
  • 韦达定理
  • 一元二次方程的判别式、求根公式等
  • 一些卡常小技巧

题意

给出分数 ab\frac{a}{b}，我们想要将它拆成若干个埃及分数（分子为 11 的真分数）之和。要求：
  • 真分数两两不同
  • 拆出来的分数最少
  • 其中最小的分数最大
求出一种拆分方案。
数据范围：1<a<b<1031<a<b<10^3，且答案满足最小的分数大于等于 1107\frac{1}{10^7}。

100pts，hack TLE

首先有一个小结论：分数数量不超过 1010 个。下面有一个感性证明。
感性证明
对于一个分数，如果想让它拆出来的分数更多，分数就要大。因为是真分数，越大就越接近 11。这里以 a1000\frac{a}{1000} 举例。
对于它，我们可以先拆成 aa 个 11000\frac{1}{1000} 之和。接着，我们分别将 1,2,4,8,…1,2,4,8,\dots 个 11000\frac{1}{1000} 合并，这样就把它分成了 11000+21000+41000+…\frac{1}{1000}+\frac{2}{1000}+\frac{4}{1000}+\dots。显然，根据倍增思想，大概只会拆出来 log⁡2b\log_2 b 个埃及分数，再加上剩余的最多 11 个，最多也只有 1010 个分数。
得证。
这么小，考虑搜索拆分的数。但关于用哪种搜索方式，有一个问题：
  • 如果使用 dfs，可能会陷入一个错解出不来
  • 如果使用 bfs，那样搜索树的深度最大为 10310−7=1010\frac{10^3}{10^{-7}}=10^{10}，空间会炸
这里隆重推荐 IDDFS，迭代加深搜索。它的思想是规定一个在搜索树上从下搜索的深度，如果超过深度直接停止搜索。你应该对它有所了解。在这道题中，深度等价于拆出的分数个数。
由于分数个数很少，我们可以记录下来我们分别选了哪些分数。显然，我们如果当前要凑出 ab\frac{a}{b}，就可以枚举所有小于它的埃及分数。我们可以缩小枚举的分母的上下界来优化。（详细讨论见下）
注意开 long long 和约分。
代码及详细讲解
下面有一些为了表述方便而制定的规定。
规定
  • 搜索状态 dfs(a,b,x,dep)：需要凑出 ab\frac{a}{b}，当前搜索进行到了 xx 层，最大为 depdep 层。
  • fmfm 数组：记录当前拆分出来的分数的分母
  • ansans 数组：记录拆分的最优答案
  • foundfound 变量：当前有没有找到一个解（不需要最优）
  • 一个解：一种满足条件的拆分方案
此外，后文中类似 ab\frac{a}{b} 的分子不为 11 的分数，如果没有特殊说明都表示 1⌊ba⌋\frac{1}{\left \lfloor \frac{b}{a} \right \rfloor}。
对当前的搜索情况分类讨论：（这一坨是重点，对于正解有很大帮助，建议配合代码理解）
  • 如果 a=1a=1，那么可能加上一个 1b\frac{1}{b} 就能得到最优解。这样，如果当前没有解，或者当前有了解，但是不如这个解更优，那么这是一个更优的解，就把 fmfm 数组赋值到 ansans。
  • 否则，需要枚举这一步拆分的分数分母。求出来这个分母的上下界，进行更深一层的搜索即可。下面是对上下界的讨论。
    • 对于下界 ll，为了保证拆分方案的递减，应该从前一个拆分出来的分母 +1+1 开始。同时为了凑出来当前的 ab\frac{a}{b}，还要保证分母至少为 ⌊ba⌋\left \lfloor \frac{b}{a} \right \rfloor。两个数取较大值即可。
    • 对于上界 rr，如果当前剩余 ab\frac{a}{b}，显然在搜索树上，从当前节点到限定深度中间会经过 dep−x+1dep-x+1 个点（类比一条从当前节点往下垂的链），考虑极端情况，中间这条链全拆出了最大值 ab\frac{a}{b}（分母为 ⌊ba⌋\left \lfloor \frac{b}{a} \right \rfloor），那么为了保证能拆出这么多分母，当前节点的分母就要取到 (dep−x+1)×⌊ba⌋(dep-x+1)\times\left \lfloor \frac{b}{a} \right \rfloor。此外，如果发现已经有了解，那么根据最优性剪枝，搜索劣于目前最优解肯定对于找到最优解无用，所以直接从优于最优解的分母开始搜索即可。
那么，找到上下界后，就可以枚举这次拆分的分母继续搜索就行了。注意范围是 [l,r)[l,r)，因为 rr 是取不到的极端情况。
我真不知道怎么才能说得更详细了，还是看代码吧（逃
警告
  • 代码中使用了 #define int long long
  • 代码只给出了关键部分。
代码
record
CPP
int a,b,g;
int fm[15],ans[15];
bool found=0;//有没有找到解
void dfs(int a,int b,int x,int dep){
	if(x>dep) return;//层数超过了dep还没有找到解，直接停止
	if(a==1&&b>fm[x-1]){//只剩1/b就能凑出答案 
		fm[x]=b;
		if(!found||b<ans[x]){//暂时没有解，或者最小分数1/b比之前的结果更大 
			up(i,1,x) ans[i]=fm[i];//复制答案 
			found=1;
			return;
		}
	} 
	int l=max(b/a,fm[x-1]+1);//分母下界
	int r=(dep-x+1)*b/a;//分母上界：假设儿子都是a/b，显然不可能 
	if(found) r=min(r,ans[dep]-1);//之前有过解，不用再搜索比之前的解更差的解，把上界调低
	up(i,l,r-1){//枚举放入的1/i，不可能达到r 
		fm[x]=i;//选择1/i 
		g=__gcd(a*i-b,b*i);
		dfs((a*i-b)/g,b*i/g,x+1,dep);//a/b-1/i=(a*i-b)/b*i
	} 
}
void Main(int cases){
	a=read(),b=read();g=__gcd(a,b);
	a/=g,b/=g;fm[0]=1;
	up(d,1,10){//枚举分数个数 
		dfs(a,b,1,d);//需要凑出a/b，当前在第一层（根），最多到第d层 
		if(found){
			up(i,1,d) cout<<ans[i]<<' ';
			return;
		}
	}
	return;
}
hack 全部超时，考虑剪枝。

第一个剪枝

我们发现搜索树的深度虽然被 IDDFS 限定了，但是宽度依旧很大。考虑同时限定搜索树的宽度，即限定最小的拆分出来的分数。
具体地，我们从搜索参数中加上一个 maxbmaxb，

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...