前言

偶然做到这题，看到讨论区有一个 hack 将所有的题解都叉掉了，因此就想用我的代码通过这个 hack。经过了两天的优化，代码终于过了。

思路

首先发现题目要求单位分数的个数最少，且直接 dfs 可能会进入一个错解出不来，bfs 会空间超限，所以使用迭代加深搜索，从小到大枚举选的分数个数 cntcnt，并 dfs。

注意到题目也要求最大的分母最小，且如果限制了分母的最大值有利于剪枝，所以也将最大的分母迭代加深，设限制为 axax，axax 从 103103 到 107107 每次乘 1010。

可以参考下面这个代码理解一下。代码中 ch 表示当前选的数，ans 表示答案选的数。

void dfs(int now,int a,int b)
{
	if(now==cnt+1)
	{
		if(a!=0) return;
		if(ans[1]==0 || ch[cnt]<ans[cnt])
		{
			for(int i=1; i<=cnt; ++i) ans[i]=ch[i];
		}
		return;
	}
	for(int i=ch[now-1]+1; i<=ax; ++i)
	{
		int gta=a*i-b,gtb=b*i,g=gcd(gta,gtb);
		gta/=g,gtb/=g;
		ch[now]=i,dfs(now+1,gta,gtb);
	}
}

这样并不能通过，考虑优化代码。以下是我加的几个优化：（因为我是在别的地方打的文本，可能有些思路展现得不是很清楚，见谅哈！）

• 设接下来选的分数为 1ii1​，则 ab≥1iba​≥i1​，所以 i≥bai≥ab​。

• 因为后面选的分数一定小于当前，所以必须满足 (cnt−now+1)⋅1i≥ab(cnt−now+1)⋅i1​≥ba​ 才有可能满足。因此 i≤(cnt−now+1)⋅bai≤a(cnt−now+1)⋅b​。

• 当 now≤cnt−1now≤cnt−1 时，需要满足下一次 ii 存在（下一次 ii 的限制区间左端点小于等于右端点）。因为 ii 的限制有关 a,ba,b 的都是两个数的比例（abba​ 或 baab​），所以在考虑下一次的时候 a,ba,b 不需要约分。设下一次的 a,ba,b 为 nxta,nxtbnxta,nxtb。提出来 nxtbnxta≤inxtanxtb​≤i 和 i≤axi≤ax 这两个条件，得 nxtbnxta≤axnxtanxtb​≤ax，即 biai−b≤axai−bbi​≤ax。所以 i≥axbaxa−bi≥axa−baxb​。

• 用类似的方法推 now≤cnt−2now≤cnt−2（axbiax(ai−b)−bi≤axax(ai−b)−biaxbi​≤ax）可以得到 i≥axbaxa−2bi≥axa−2baxb​。因此猜测对于任意的 nownow 都有 i≥axbaxa−(cnt−now)bi≥axa−(cnt−now)baxb​。使用类似的方法可以证明。

• 假设 cnt=3cnt=3，那么 ab=1x+1y+1z=xy+xz+yzxyzba​=x1​+y1​+z1​=xyzxy+xz+yz​。又因为 x,y,z≤axx,y,z≤ax，所以若 a>cnt⋅ax2a>cnt⋅ax2 或 b>ax3b>ax3，则无解。类似的，若在过程中 a>(cnt−now+1)⋅axcnt−nowa>(cnt−now+1)⋅axcnt−now 或 b>axcnt−now+1b>axcnt−now+1 则无解。

• 当 now=cntnow=cnt 时，最后一个分数一定为 abba​，所以直接检查是否合法即可，不需要递归到下一层。

• 当 now=cnt−1now=cnt−1 时，还剩下两个分数。设 ab=1x+1y=x+yxyba​=x1​+y1​=xyx+y​。所以 a,ba,b 同时乘上某个数（设其为 zz）后分别等于 x+y,xyx+y,xy。因为 x+y≤2axx+y≤2ax，所以 z≤2axaz≤a2ax​，并不会太大。因此当 zz 小于等于某个阈值时，可以直接枚举 zz，并解方程组 {az=x+ybz=xy{az=x+ybz=xy​ 即可得到最后两个分数，检查是否合法即可。

• 在上面优化的过程中，方程有不相等的两解当且仅当 Δ=(az)2−4bz>0Δ=(az)2−4bz>0 即 z>4ba2z>a24b​，因此枚举的时候下界为 ⌊4ba2⌋+1⌊a24b​⌋+1。

使用这些优化后，便可以快速通过讨论区的 hack。

代码

代码中使用了 __int128，因为不确定是否会爆 long long。

#include<bits/stdc++.h>
using namespace std;
#define int __int128
int ceil(int a,int b) { return (a+b-1)/b; }
int gcd(int a,int b) { return b==0?a:gcd(b,a%b); }
int a,b;
int cnt,ax;
int ch[1000010],ans[1000010];
int ppow[1000010];
int sum=0;
void dfs(int now,int a,int b)
{
    if(now==cnt-1 && min(ax*2/a,ax*ax/b)<=1000)
    {
        int tmp=min(ax*2/a,ax*ax/b);
        for(int i=(4*b/a/a)+1; i<=tmp; ++i)
        {
            int delta=a*i*a*i-4*b*i;
            int sqr=sqrtl((long double)delta)+2;
            while(sqr*sqr>delta) --sqr;
            if(sqr*sqr!=delta || (a*i+sqr)%2!=0) continue;
            ch[cnt-1]=(a*i-sqr)/2,ch[cnt]=(a*i+sqr)/2;
            if(ch[cnt-1]>ch[cnt-2] && ch[cnt]>ch[cnt-1] && ch[cnt]<ax)
            {
                ax=ch[cnt];
                for(int i=1; i<=cnt; ++i) ans[i]=ch[i];
                for(int i=1; i<=cnt; ++i) ppow[i]=min(ppow[i-1]*ax,(int)1e29);
            }
        }
        return;
    }
    if(now==cnt)
    {
        if(b%a!=0 || b/a<=ch[cnt-1]) return;
        ch[cnt]=b/a;
        if(ch[cnt]<ax)
        {
            ax=ch[cnt];
            for(int i=1; i<=cnt; ++i) ans[i]=ch[i];
            for(int i=1; i<=cnt; ++i) ppow[i]=min(ppow[i-1]*ax,(int)1e29);
        }
        return;
    }
    if(a>(cnt-now+1)*ppow[cnt-now] || b>ppow[cnt-now+1]) return;
    int l=max(ch[now-1]+1,max(ceil(b,a),ceil(b*ax,a*ax-(cnt-now)*b))),r=min(ax,(cnt-now+1)*b/a);
    if(now==cnt-1)
    {
        for(int i=l; i<=r; ++i) ch[now]=i,dfs(now+1,a*i-b,b*i);
    }
    else
    {
        for(int i=l; i<=r; ++i)
        {
            ch[now]=i;
            int g=gcd(a*i-b,b*i);
            dfs(now+1,(a*i-b)/g,b*i/g);
        }
    }
}
signed main()
{
    ppow[0]=1;
    long long re; cin>>re; a=re; cin>>re; b=re;
    int g=gcd(a,b); a/=g,b/=g;
    if(a==1) return cout<<(long long)b,0;
    cnt=2;
    while(1)
    {
        ans[cnt]=1e9;
        ax=1e3;
        while(ax<=1e7)
        {
            for(int i=1; i<=cnt; ++i) ppow[i]=min(ppow[i-1]*ax,(int)1e29);
            dfs(1,a,b);
            if(ans[1]!=0 && ans[1]!=1e9)
            {
                for(int i=1; i<=cnt; ++i) cout<<(long long)ans[i]<<' ';
                return 0;
            }
            ax*=10;
        }
        ++cnt;
    }
    return 0;
}