埃及分数

问题：

 0 Your sequence is longer than the standard answer!QAQ 

代码：

#include<bits/stdc++.h>
using namespace std;
bool flag=false;
long long ans[10000];
long long num[10000];
long long deep;
long long maxi;
long long minlo=1000;
long long gcd(long long a,long long b){
    return b==0?a:gcd(b,a%b);
}
struct fs{
    long long fz,fm;
    fs operator-(const fs x)const{
        long long g=gcd(fm,x.fm);
        long long new_fm=fm/g*x.fm;
        long long new_fz=fz*(new_fm/fm)-x.fz*(new_fm/x.fm);
        if(new_fz<=0)return{0,1};
        long long g2=gcd(new_fz,new_fm);
        return {new_fz/g2, new_fm/g2};
    }
};
void dfs(long long lev,fs f){
    if(lev>deep)return;
    if(f.fz==1&&f.fm>num[lev-1]&&f.fm<=1e7){
        num[lev]=f.fm;
        if(!flag||num[lev]<ans[lev]){
            for(long long i=1;i<=lev;i++)ans[i]=num[i];
            flag=true;
        }
        return;
    }if(lev==deep){
        if(f.fz!=1||f.fm>1e7)return;
        if(!flag||num[lev]<ans[lev]){
            for(long long i=1;i<=lev;i++)ans[i]=num[i];
            flag=true;
        }return;
    }
    if(lev==deep-1){
        long long l=(f.fm<<2)/f.fz/f.fz+((f.fm<<2)%(f.fz*f.fz)!=0);
        long long maxbb=min(min((long long)(2e7/f.fz),(long long)(2e14/f.fm)),(long long)(1e7));
        long long r=min((maxbb<<1)/f.fz,maxbb*(maxbb-1)/f.fm);
        for (int k=l;k <=r;k++){
            long long delta=f.fz*f.fz*k*k-(f.fm<<2)*k;
            if(delta<=0)continue;
            long long d=sqrt(delta);
            if(d*d!=delta||(f.fz*k+d)&1)continue;
            long long x1=(f.fz*k-d)>>1;
            if(x1<=num[lev-1]||x1>1e7)continue;
            long long x2=(f.fz*k+d)>>1;
            if(x2<=0||x1<=0||x2>1e7)continue;
            if(flag&&x2>=ans[deep])break;
            if(((!ans[lev]||x2<ans[deep])&&x1>num[lev-1]&&x2>x1&&deep<=minlo)&&deep<=minlo){
                num[deep-1]=x1,num[deep]=x2;
                for(int i=1;i<=deep;i++)ans[i]=num[i];
                minlo=deep;
                flag=true;
                return;
            }
        }
        return;
    }
    long long l=max(num[lev-1]+1,(f.fm+f.fz-1)/f.fz);
    long long r=min((long long)(1e7),(deep-lev+1)*f.fm/f.fz);
    if(flag)r=min(r,ans[deep]-1);
    for(long long i=l;i<=r;i++){
        fs n_fs=f-(fs){1,i};
        if(n_fs.fz<=0)continue;
        num[lev]=i;
        dfs(lev+1,n_fs);
    }
}
int main(){
    long long a,b;
    scanf("%lld %lld",&a,&b);
    maxi=b*1e7;
    fs f={a,b};
    deep=1;
    while(deep<100){
        dfs(1,f);
        if(ans[deep]>1e7)flag=false;
        if(flag){
            for(int i=1;i<=deep;i++)cout<<ans[i]<<" ";
            return 0;
        }
        ++deep,flag=false;
    }
    return 0;
}