hack点没过,讨论区的大佬们讲的看不懂,能把我的代码改对的得一关
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll a, b, gcd, dep, num[11], ans[11];
bool can;
void dfs(ll a, ll b, ll x)
{
if (x > dep) return;
if (a == 1 && b > num[x - 1])
{
num[x] = b;
if (can == 0 || num[x] < ans[x])
for (int i = 1; i <= dep; i++)
ans[i] = num[i];
can = 1;
return;
}
ll l = max(b / a, num[x - 1] + 1), r = (dep - x + 1) * b / a;
if (can && r >= ans[dep]) r = ans[dep] - 1;
for (ll i = l; i < r; i++)
{
num[x] = i;
ll tmp = __gcd(a * i - b, b * i);
dfs((a * i - b) / tmp, (b * i) / tmp, x + 1);
}
}
int main()
{
cin >> a >> b;
gcd = __gcd(a, b);
a /= gcd, b /= gcd;
num[0] = 1;
for (dep = 1; dep <= 10; dep++)
{
dfs(a, b, 1);
if (can)
{
for (int i = 1; i <= dep; i++) cout << ans[i] << ' ';
break;
}
}
return 0;
}