关于迭代加深,个人认为和dfs的区别在于如果知道答案的深度可以用dfs,相反如果不知道深度的话可以考虑用迭代加深。
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
int Case = 1;
ll n, m;
ll up;
ll res[maxn], v[maxn];
ll ask_min(ll a, ll b) {
for(ll i = 2;; i++) {
if(i*a >= b) return i;
}
}
ll gcd(ll a, ll b) {
return (b==0)?a:gcd(b, a%b);
}
bool better(int d) {
for(int i = d; i >= 1; i--) {
if(res[i] != v[i])return res[i] == -1||v[i]<res[i];
}
return false;
}
bool dfs(ll dep, ll mi, ll a, ll b) {
if(dep == up) {
if(b%a) return false;
v[dep] = b/a;
if(better(dep)) {
for(int i = 1; i <= dep; i++) {
res[i] = v[i];
}
}
return true;
}
bool ok = false;
mi = max(mi, ask_min(a, b));
for(ll i = mi;; i++) {
if(b*(up-dep+1) <= i*a) break;
v[dep] = i;
ll b2 = b*i, a2 = a*i-b, g = gcd(a2, b2);
if(dfs(dep+1, i, a2/g, b2/g)) ok = true;
}
return ok;
}
void solve() {
scanf("%lld%lld", &n, &m);
if(m%n == 0) {
printf("%lld\n", m/n);
return;
}
ll x = ask_min(n, m);
memset(res, -1, sizeof(res));
for(up = 2;; up++) {
if(dfs(1, x, n, m)) break;
}
for(int i = 1; i <= up; i++)
printf("%lld%c", res[i], i == up?'\n':' ');
return;
}
int main() {
while(Case--) {
solve();
}
return 0;
}