srds,我好像 btd 了,我好像去年就会了诶,只是今天才意识到应该写一下(
目前想到的剪枝全加上了,不知道为什么假了
#include<stdio.h>
#include<stack>
typedef unsigned long long ll;
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
struct frac{
ll a{0},b{1};
frac&update(){ll d=gcd(a,b);return a/=d,b/=d,*this;}
frac(ll x,ll y):a(x),b(y){update();}
frac&operator-=(const frac&o){
ll d=gcd(b,o.b);
return a=o.b/d*a-b/d*o.a,b=b/d*o.b,update();
}
bool operator<(const frac&o)const{ll d=gcd(b,o.b);return o.b/d*a<b/d*o.a;}
};
std::stack<int>res;
bool iddfs(frac x,int s,int limit){
x-=frac(1,s);
if(x.a==0)return 1;
if(s==limit)return 0;
int l=s+1,r=limit;
if(x<frac(1,limit))return 0;
for(;l<r;){
int mid=l+r>>1;
if(x<frac(1,mid))l=mid+1;
else r=mid;
}
for(s=l;s<=limit;++s){
if(frac(limit-s+1,s)<x)return 0;
if(iddfs(x,s,limit))
return res.push(s),1;
}
return 0;
}
bool IDDFS(frac x){
for(int i=1;i<=10000000;++i)
for(int j=1;j<=i;++j){
if(frac(i-j+1,j)<x)break;
if(iddfs(x,j,i))
return res.push(j),1;
}
return 0;
}
int main(){
int a,b;
scanf("%d%d",&a,&b);
IDDFS(frac(a,b));
for(;!res.empty();res.pop())printf("%d ",res.top());
return 0;
}