#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int maxd;
const int maxn=
1000000;
int best[maxn];
int ans[maxn];
int first(
int a,
int b)
{
int it=
1;
while(
1)
{
if(a*it-b>
0)
return it;
else it++
;
}
}
int gcd(ll a,ll b)
{
return b==
0? a:gcd(b,a%
b);
}
bool updatep(
int d)
{
for(
int i=d;i>=
0;i--
)
if(ans[i]!=best[i])
return (best[i]==-
1 || ans[i]<
best[i]);
return false;
}
bool dfs(
int d,
int from,ll a,ll b)
{
if(d==
maxd)
{
if(b%a)
return false;
ans[d]=b/
a;
if(updatep(d)) memcpy(best,ans,
sizeof(ll)*(d+
1));
return true;
}
from=max(
from,first(a,b));
bool ok=
false;
for(
int i=
from;;i++
)
{
if((maxd+
1-d)*b<=a*i)
break;
ans[d]=
i;
ll a2=a*i-
b;
ll b2=b*
i;
ll g=
gcd(a,b);
if(dfs(d+
1,i+
1,a2/g,b2/g)) ok=
true;
}
return ok;
}
int main()
{
ll a,b;
cin>>a>>
b;
int ok=
0;
for(maxd=
1;;maxd++
)
{
memset(best,-
1,
sizeof(best));
if(dfs(
0,first(a,b),a,b))
{
ok=
1;
break;
}
}
if(ok)
for(
int i=
0;i<=maxd;i++
)
printf("%d ",best[i]);
else
printf("-1");
printf("\n");
return 0;
}
转载于:https://www.cnblogs.com/tclan126/p/7452224.html
