P1763 埃及分数

#include <iostream>
#include <cstring>
#include <string>
using namespace std;
typedef long long ll;
ll a , b , md ;
ll ans [ 100000 ] , s [ 100000 ] ;
ll gcd ( ll x , ll y ) { return y == 0 ? x : gcd ( y , x % y ) ; }
void hj ( ll & x , ll & y ) { ll t = gcd ( x , y ) ; x /= t ; y /= t ; } 
ll findanumber ( ll x , ll y ) {
	ll _ = y / x ;
	if ( _ * x < y ) _ ++ ;
	return _ ;
}
bool dfs ( ll now , ll x , ll y , ll pre ) {
	if ( now == md ) {
		hj ( x , y ) ;
		if ( x != 1 ) return false ; 
		s [ now ] = y ; 
		bool flag = false ; 
		for ( ll i = now ; i >= 1 ; i -- ) 
			if ( ans [ i ] != s [ i ] ) { flag = ( ans [ i ] == -1 || s [ i ] < ans [ i ] ) ; break ; }
		if ( flag ) {
			for ( ll i = 1 ; i <= now ; i ++ ) 
				ans [ i ] = s [ i ] ;
		}
		return true ; 
	}
	bool flag = false ; 
	ll mt = max ( pre , findanumber ( x , y ) ) ;
	for ( ; ; mt ++ ) {
		if ( mt * x >= y * ( md - now + 1 ) ) break ;
		s [ now ] = mt ;
		ll xx = x * mt - y , yy = y * mt ;
		hj ( xx , yy ) ;
		if ( dfs ( now + 1 , xx , yy , mt + 1 ) ) flag = true ;
	}
	return flag ; 
}
int main ( ) {
	cin >> a >> b ;
	hj ( a , b ) ;
	if ( a == 1 ) { cout << b << endl; return 0 ; }
	md = 1 ; 
	while ( ++ md ) {
		memset ( ans , -1 , sizeof ( ans ) ) ;
		if ( dfs ( 1 , a , b , findanumber ( a , b ) ) ) {
			for ( ll i = 1 ; i <= md ; i ++ ) cout << ans [ i ] << " " ;
			cout << endl;
			return 0 ;
		}
	}
	return 0 ;
}