第七章埃及数

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;
int maxd;
const int maxn=1000000;
int best[maxn];
int ans[maxn];

int first(int a,int b)
{
    int it=1;
    while(1)
    {
        if(a*it-b>0) return it;
        else it++;
    }
}

int gcd(ll a,ll b)
{
    return b==0? a:gcd(b,a%b); 
}

bool updatep(int d)
{
    for(int i=d;i>=0;i--)
        if(ans[i]!=best[i]) return (best[i]==-1 || ans[i]<best[i]);
    
    return false;
}

bool dfs(int d,int from,ll a,ll b)
{
    if(d==maxd)
    {
        if(b%a) return false;

        ans[d]=b/a;

        if(updatep(d)) memcpy(best,ans,sizeof(ll)*(d+1));

        return true;
    }

    from=max(from,first(a,b));
    bool ok=false;

    for(int i=from;;i++)
    {
        if((maxd+1-d)*b<=a*i) break;

        ans[d]=i;

        ll a2=a*i-b;
        ll b2=b*i;
        ll g=gcd(a,b);

        if(dfs(d+1,i+1,a2/g,b2/g)) ok=true;
    }

    return ok;
}

int main()
{
    ll a,b;
    cin>>a>>b;

    int ok=0;
    for(maxd=1;;maxd++)
    {
        memset(best,-1,sizeof(best));

        if(dfs(0,first(a,b),a,b))
        {
            ok=1;
            break;
        }
    }

    if(ok)
        for(int i=0;i<=maxd;i++)
            printf("%d ",best[i]);
    else
        printf("-1");

    printf("
");

    return 0;
}