ID搜索

ID搜索"/>

ID搜索

埃及分数

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<set>
#include<cmath>
using namespace std;int a,b,k,depth;
vector<int>tmp,ans;
bool flag;int gcd(int a,int b){return !b?a:gcd(b,a%b);
}bool check(){for(int i=depth;i>=0;i--)if(tmp[i]!=ans[i])return ans[i]==-1 || tmp[i]<ans[i];return 0;
}void dfs(int a,int b,int dep){if(dep>depth ||  a==0)	return;if(b%a==0 && (b/a)>tmp[dep-1]){tmp.push_back(b/a);if(!flag || check()) ans=tmp,flag=1;tmp.pop_back();return;}int s=ceil(1.0*b/a);(dep>0 && s<=tmp[dep-1]) && (s=tmp[dep-1]+1);int t=ceil(1.0*b*(depth-dep+1)/a);if(flag && t>=ans[depth]) t=ans[depth]-1;for(int i=s;i<=t;i++){int GCD=gcd(a*i-b,b*i);tmp.push_back(i);dfs((a*i-b)/GCD,b*i/GCD,dep+1);tmp.pop_back();}
}int main(){flag=0;scanf("%lld%lld",&a,&b);for(depth=1;;depth++){dfs(a,b,0);if(flag) break;}printf("%d",ans[0]);for(int i=1;i<=depth;++i)printf(" %d",ans[i]);  
}