#include #include #include using namespace std;typedef long long ll;ll depth,a,b,flag,ans[100005],nans[100005];inline ll gcd(ll a,ll b){ return b?gcd(b,a%b):a; }inline void yuefen(ll &a,ll &b){ll eaa=gcd(a,b);a/=eaa;b/=eaa;}inline void dfs(ll now,ll shen_fz,ll shen_fm,ll last_fm){ yuefen(shen_fz,shen_fm);//在上面统一约分多省事啊哈哈哈 if(now==depth){ if(shen_fz==1&&shen_fm>last_fm){ if(flag&&shen_fm>=ans[depth])return;//要比较取优，因为最大的分母是算出来的不是搜出来的 nans[depth]=shen_fm; flag=1; memcpy(ans,nans,sizeof(nans)); } return; } for(ll i=last_fm+1;i<=ceil((double)(depth-now+1)*shen_fm/shen_fz);i++){ //i=last_fm+1使搜出来的分母递增，所以说都是要这样搜啊QAQ //(depth-now+1)*shen_fm/shen_fz是趋近的最大值,即限制能否在depth内把shen的分数拆分完 //其实好像可以判断一下就是(i>=shen_fm/shen_fz才可以)，跟最后一个注释同理，亲测确实快一点 nans[now]=i; dfs(now+1,shen_fz*i-shen_fm,shen_fm*i,i); }}int main(){ scanf("%I64d%I64d",&a,&b);//好吧其实在loj上忘了改成lld while(++depth){ dfs(1,a,b,b/a-1);//b/a是第一个分母的最小值，第一个分母不用从1开始搜的 if(flag){ for(ll i=1;i<=depth;i++)printf("%I64d ",ans[i]); return 0; } }}
好吧算是比较易懂了
参考文献：