做完后发现很多题解都是有些细节问题的，对于向上与向下取整非常混乱。
第一次做迭代加深搜索的题，记录一下。
所谓迭代加深搜索，就是在求搜索树的深度的问题中，枚举层数，取最优解。
然而广搜其实感觉上能做到，但广搜在分支太多的情况下，容易爆栈，所以推出了迭代加深搜索。
本题一来肯定想到爆搜，很好的拿到 \(10pts\)。
然后学习到了迭代加深搜索，因为本题优先使分解的数个数最少，相当于求 \(1e7\) 叉搜索树的最小深度，所以可以优先进行分层搜索。
但貌似没什么用，仍然是 \(10pts\)。
考虑剪枝。
1.最优性剪枝
在同一层的情况下，若枚举到的最大分母大于了之前答案的最大分母，那么本次肯定不能更新答案，直接退出。
2.无效性剪枝
对于枚举中分数的和已大于目标分数，不可能达到，舍去。
3.优化搜索顺序
从小到大进行搜索，避免重复。
进行了三次优化后分数依然没变，为 \(10pts\)。
此时应该发现了，本题搜索的最大关键是因为搜索分支过多，导致效率低下。所以最重要的应该是想办法去处大量的无效性分支，所以应该进行第二次无效性剪枝。
首先是搜索上界，由于搜索顺序被优化，搜索是从小到大进行，所以如果前面的分数过小，后面的分数再大，也无法凑成目标分数。
所以我们可以列出一个式子
\(\frac{1}{i}> \frac{a}{b}\div step \hspace{0.1cm}\text{（其中}\hspace{0.1cm}step \hspace{0.1cm}\text{代表剩余需要分解的分数个数）}\)
两边倒数后
\(i<\frac{b\times step}{a}\)
其实后来发现可以取等，虽然会因为有重复数字造成影响，但我们不妨假设
\(i=\frac{b\times step}{a}\)
那么取了分数 \(\frac{1}{i}\) 后，必定与目标分数相等，那么这个深度在枚举此深度之前就已经搜到可行解了，此次解必定不是最优，直接舍去，所以可以取等。
\(i\le\frac{b\times step}{a}\)
那么右式可以直接向下取整，不需要利用精度去计算。
处理上界完毕后得分为 \(30pts\)。
模拟题目中有一个例子 \(a=59,b=211\) 可以发现因为现分数和大于目标分数的情况十分多，所以只有这样回溯不是最优的，我们应该处理下界。
下界就更简单了，当 \(\frac{1}{i}>\frac{a'}{b'}\hspace{0.3cm}\frac{a'}{b'}\hspace{0.1cm}\text{（代表减去之前枚举过的分数后的剩余分数）}\) 时，直接减去这种情况。
所以下界就是第一个满足 \(\frac{1}{i}\le \frac{a'}{b'}\) 的 \(i\)。
取倒数后 \(i\ge\frac{b'}{a'}\)。
可以取等的证明同上，右式可以向上取整，不用处理精度问题。
然后就AC了，十分不容易。
#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
int a,b,t[1005],p[1005];
int ans;
int gcd(int x,int y)
{
if(y==0)return x;
return gcd(y,x%y);
}
bool dfs(int step,int bef=1,int x=a,int y=b)
{
if(bef>t[1])return 0;
if(step==0&&x==0)
{
for(int i=1;i<=ans;i++)t[i]=p[i];
return 1;
}
if(step==0)return 0;
bool flag=0;
bef=max(bef,(y+x-1)/x);
for(int i=bef;(y*step)/x>=i;i++)
{
int num=gcd(y,i);
if(num>1e7)continue;
p[step]=i;
bool s=dfs(step-1,i+1,x*i/num-y/num,y/num*i);
flag|=s;
}
return flag;
}
signed main()
{
scanf("%lld%lld",&a,&b);
for(int i=1;i<=1000;i++)t[i]=1e9;
while(++ans)if(dfs(ans))break;
for(int i=ans;i>0;i--)printf("%lld ",t[i]);
return 0;
}