题目描述

在古埃及,人们使用单位分数的和 (形如 1/a 的, a 是自然数) 表示一 切有理数。如:2/3=1/2+1/6, 但不允许2/3=1/3+1/3, 因为加数中有相同的。对于一个分数 a/b,表示方法有很多种,但是哪种最好呢?首先,加数少的比加数多的好,其次,加数个数相同的,最小的分数越大越好。
如:
• 19/45=1/3 + 1/12 + 1/180
• 19/45=1/3 + 1/15 + 1/45
• 19/45=1/3 + 1/18 + 1/30,
• 19/45=1/4 + 1/6 + 1/180
• 19/45=1/5 + 1/6 + 1/18.
最好的是最后一种,因为 1/18 比 1/180,1/45,1/30,1/180 都大。

输入

一行两个整数 a,b。

输出

若干个数,自小到大排列,依次是单位分数的分母。

样例输入

19 45

样例输出

5 6 18

题解

迭代加深搜索

从小到大枚举当前分母值，要求分母大小递增，且最大的分母越小越好（最小的分数越大越好）
加上两个剪枝来减小枚举分母的范围，若要分解$\frac{a}{b}$，还剩x个数，

• 则最大的分母不会大于⌈$\frac{bx}{a}$⌉，
• 最小不会小于⌊$\frac{b}{a}$⌋

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<cmath>
#include<string>
using namespace std;
#define ios ios::sync_with_stdio(false)
const double pi=acos(-1.0);
int dx[]={-1,0,1,0,0},dy[]={0,1,0,-1,0};
typedef pair<int,int> PII;
typedef pair<double,double> pdd;
typedef pair<double,int> pdi;
typedef long long LL;
const int INF=0x3f3f3f3f;
const LL IINF=0x3f3f3f3f3f3f3f3f;

const int N=1010;
LL path[N],ans[N];
int a,b;
int dep=1;

LL gcd(LL a,LL b)
{
    return b?gcd(b,a%b):a;
}

bool dfs(int u,LL x,LL y,LL last)//u：层数，x/y：剩下的分数值，last：上一次分解的分母
{
    if(u == dep)
    {
        if(x == 1)
        {
            path[u]=y/x;
            if(!ans[u] || ans[u] > path[u])
            {
                for(int i=0;i<=dep;i++)
                    ans[i]=path[i];
                return true;
            }
        }
        return false;
    }

    bool flag=false;
    for(int i=max(last,y/x)+1;i<y/x*(dep-u+1);i++)
    {
        LL nowx=x*i-y;
        LL nowy=y*i;
        LL g=gcd(nowx,nowy);
        nowx/=g,nowy/=g;
        path[u]=i;
        if(dfs(u+1,nowx,nowy,i)) flag=true;
    }
    return flag;
}

int main()
{
    cin>>a>>b;
    int g=gcd(a,b);
    a/=g,b/=g;

    while(1)
    {
        if(dfs(0,a,b,b/a)) break;
        dep++;
    }

    for(int i=0;i<=dep;i++)
        cout<<ans[i]<<' ';
    cout<<endl;

    // system("pause");
}