P1763 埃及分数 [题解]
NianFeng
·
·
题解
blog食用地址：广告
阅读理解：
给定一个分数 \frac{a}{b}，用若干个 \frac{1}{x} 凑出 \frac{a}{b}，不可相同且越少越好，并让最小的最大。其中，x<10^7。
看到一个词：
脑袋开窍：这是一道简单的类似全排列搜索题！
那么，省选/NOI-从何而来？先放一边，开始思考。
既然是搜索，从 dfs 入手：类似全排列，step 代表当前搜索到第几个数，sum 代表目前总和。BUT，如下：
P1706 全排列问题
void dfs(int step){
if(step>n){
for(int i=1;i<=n;i++)
cout<<" "<<tmp[i];
cout<<endl;
return;
}
for(int i=1;i<=n;i++){
if(!vis[i]){
vis[i]=true;
tmp[step]=i;
dfs(step+1);
vis[i]=false;
}
}
}
可以看出，当 step > n 时，程序即得出答案，也就是说，普通的 dfs 的搜索树深度是有限滴！再看题目，“若干个”，很好，搜索树深到离谱（已经冲破这个宇宙了）
回头再看某 bfs，若每次加进去的状态为 now + \frac{1}{x}，又暮然回首，“x<10^7”……
内存：去死吧，queue！
queue：别说了，我已经死了。
好吧，搜索是不可能搜索的，那么，从人的角度看，如果让你来做这题，应该是这样的：
看看这个思路，从一个搜起，一次一次增加 $\frac{1}{x}$ 的个数，直到搜索到为止。这样的搜索算法，就叫 **IDS 或 IDDFS**（Iterative Deepening Depth First Search，**迭代加深搜索**）。
# 正片开始
[前置芝士](https://www.luogu.com.cn/paste/x0koghf6)：由于本题涉及到约分与化简，你要知道 [gcd](https://baike.baidu.com/item/%E6%9C%80%E5%A4%A7%E5%85%AC%E7%BA%A6%E6%95%B0/869308?fr=aladdin)。
涉及变量：
- $flag$，是否找到；
- $dep$，当前搜索的**最大深度**；
- $now[]$，记录搜索记录，用以**更新** $ans[]$;
- $ans[]$，答案。
既然是**迭代**搜索，搜索开始也应从1开始，一点一点加：
```cpp
for(dep=1;!flag;dep++){
dfs(a,b,1);
}
```
------------------------------进度条：10%------------------------------（就这么点）
看 dfs 部分。首先，参数定义 $a$、$b$，分别为**当前还剩的分子、分母**，$d$ 为当前深度即搜索到第几个。因为**从小到大输出**，所以每一次的 $x$ 都要大于上一个 $x$。从 $\frac{1}{2}$ 开始，那么初始化 $now[0]$ 为1。搜索的每一次都会将 $\frac{a}{b}$ 减去 $\frac{1}{x}$ 作为下一次的 $\frac{a}{b}$。计算得，下一次的 $a$、$b$ 应为 $a \times x-b$ 和 $b \times x$。
如果当 $d<dep$ 时进行判断并返回，搜索树会**增加一层**，导致效率降低，所以我们在 $d==dep$ 时进行**判断并返回**。如果当前分数能凑成的话，$\frac{a}{b}$ **必然是一个埃及分数**，即 $a==1$。而且由于我们的答案是递增的，所以 $b$ 至少**大于上一个**。最后判断最优性，更新答案，返回。基础代码就出来了：
```cpp
void dfs(int a,int b,int d){
if(d==dep){ //这里直接判断最后一个，然后返回
if(a==1&&b>now[d-1]){
now[d]=b;
if(flag&&now[d]<ans[d]||!flag)
/*分子相同，分母越大，分数越小，则now[d]和ans[d]都是各序列
中最小的，当now[d]<ans[d]时，1/now[d]一定大于1/ans[d]。*/
for(int i=1;i<=d;i++)
ans[i]=now[i];
flag=true;
}
return;
}
int low=now[d-1]+1;
int up=1e7;
for(int i=low;i<=up;i++){
now[d]=i;
int x=a*i-b,y=b*i;
int g=gcd(x,y);
dfs(x/g,y/g,d+1);
}
}
```
------------------------------进度条：75%------------------------------
**然鹅……**
编译器：（光标闪动）我停了。
看一看代码，$low$ 从 $now[d-1]+1$ 开始没问题，但是上限是 $10^7$ 啊！所以，优化是必然的。首先看一看下限，这里可以想到一个可行性剪枝。首先，我们在 $d==dep$ 时就判断返回，那么就要保证前面的分数不会让 $\frac{a}{b}$ 被取空。谨记，**分母约大，分子越小**，可以让 $\frac{a}{b}$ 当场取空的分数应该是 $\frac{1}{\frac{b}{a}}$，所以第一个优化便是 $low$ 要大于 $\frac{b}{a}$。
```cpp
int low=max(now[d-1]+1,b/a+1);
```
除了 $low$，$up$ 也可以进行剪枝。首先是最优性剪枝，为了让答案最小的最大，且搜索的 $now[]$ 单调递增，则每一次的分子应该不大于目前最优解 $ans[d]$。
```cpp
int up=1e7;
if(flag){
up=ans[dep]-1;
}
```
$up$ 也可以进行可行性剪枝。$now[]$ 是递增的，所以后面的分数越来越小。所以，本次搜索的分数最小也要是 $\frac{a}{b} \div (dep-d+1)$。不然的话，剩下的分数即使相同，也凑不成 $\frac{a}{b}$。
```cpp
up=min(up,(dep-d+1)*b/a);
```
------------------------------进度条：100% 就此完结------------------------------
AC代码：
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=10005;
namespace math{
int gcd(int a,int b){
if(b==0) return a;
return gcd(b,a%b);
}
}
using namespace math;
int a,b;
int dep;
int now[N],ans[N];
bool flag=false;
void dfs(int a,int b,int d){
if(d==dep){
if(a==1&&b>now[d-1]){
now[d]=b;
if(flag&&ans[d]>now[d]){
for(int i=1;i<=d;i++){
ans[i]=now[i];
}
}
flag=true;
}
return;
}
int low=max(now[d-1]+1,b/a+1);
int up=1e7;
if(flag){
up=ans[dep]-1;
}
up=min(up,(dep-d+1)*b/a);
for(int i=low;i<=up;i++){
now[d]=i;
int x=a*i-b,y=b*i;
int g=gcd(x,y);
dfs(x/g,y/g,d+1);
}
}
signed main(){
memset(ans,0x3f,sizeof(ans));
cin>>a>>b;
now[0]=1;
for(dep=1;!flag;dep++){
dfs(a,b,1);
}
for(int i=1;i<dep;i++){
cout<<ans[i]<<" ";
}
return 0;
}
```