评测记录

CODE

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b,c,deep,flag,num1[505],num2[505];
ll gcd(ll n,ll m){
	if(n%m==0)	return m;
	return gcd(m,n%m);
}
void dfs(ll a,ll b,ll dep){
	if(dep>deep||a<0||b>1e7)	return ;
	if(a==1&&b>num1[dep-1]){
		num1[dep]=b;
		if(!flag||num1[dep]<num2[dep]){
			for(ll i=1;i<=dep;i++){
				num2[i]=num1[i];
			}
		}
		flag=1;
		return ;
	}
	ll r=b/a*(deep-dep+1);
	if(flag&&num2[deep]<=r)	r=num2[deep]-1;
	for(ll i=max(b/a,num1[dep-1]+1);i<r;i++){
		num1[dep]=i;
		dfs((a*i-b)/gcd(a*i-b,b*i),b*i/gcd(a*i-b,b*i),dep+1);
		num1[dep]=0;
	}
	
}
int main(){
	cin>>a>>b;
	c=gcd(a,b);
	a/=c;
	b/=c;
	for(deep=0;;deep++){
		dfs(a,b,1);
		if(flag){
			for(ll i=1;i<=deep;i++){
				cout<<num2[i]<<" ";
			}
			break;
		}
	}
	return 0;
}