瞎**搜索!
暴力枚举k,对于每个k搜一遍,如果最后一层的b%a==0则有解为b/a,否则无解(易证)
每一层的分母i需大于上一层分母(效率上考虑)和b/a,由于i之后的分母大于i,则当前dep+1到k的最大和为(k-dep)/i,式子变形后可得i的上界
然后瞎**搜
1 #include<queue> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 int a,b,k; 7 long long ans[1000005]; 8 long long pre[1000005]; 9 long long gcd(long long x,long long y){ 10 if(!y){ 11 return x; 12 } 13 return gcd(y,x%y); 14 } 15 void dfs(long long c,long long d,int dep){ 16 if(d%c==0){ 17 if(ans[dep-1]==d/c)return; 18 ans[dep]=d/c;int fl=0; 19 for(int i=k;i>=1;i--){ 20 if(ans[i]>pre[dep])break; 21 if(ans[i]<pre[dep]){ 22 fl=1; 23 break; 24 } 25 } 26 if(!pre[dep]||fl){ 27 for(int i=1;i<=k;i++){ 28 pre[i]=ans[i]; 29 } 30 } 31 return; 32 } 33 if(dep==k+1){ 34 return; 35 } 36 for(long long i=min(0x3f3f3f3fll,1ll*d*(k-dep+1)/c);i>=max(d/c+1,ans[dep-1]+1);i--){ 37 ans[dep]=i; 38 long long x=1ll*c*i-d; 39 long long y=1ll*d*i; 40 long long g=gcd(x,y); 41 long long aa=x/g,bb=y/g; 42 dfs(aa,bb,dep+1); 43 } 44 return; 45 } 46 int main(){ 47 scanf("%d%d",&a,&b); 48 for(k=1;k<=1000000;k++){ 49 dfs(a,b,1); 50 if(pre[1])break; 51 } 52 for(int i=1;i<=k;i++){ 53 printf("%lld ",pre[i]); 54 } 55 return 0; 56 }