30分求调玄关
查看原帖
30分求调玄关
1052896
Balzebu楼主2024/1/26 20:55
#include <bits/stdc++.h>
using namespace std;
int depth, path[1005], maxn, ans[1005];
double cnt;
map<int, bool> mp;
map<int, bool> mpp;
int gcd (int a, int b) { return b == 0 ? a : gcd(b, a % b); }
void jian (int *a, int *b, int c) {
	if ((*b) == c) (*a)--;
	else {
		int g = gcd(max(*b, c), min(*b, c));
		int l = (*b) * c / g;
		*a = (*a) * l / (*b) - l / c;
		*b = l;
	}
}
bool dfs (int u, int a, int b) {
	if (a == 1) {
		path[u] = b;
		return true;
	}
	if (u > depth) return false;
	for (int i = max(b / a, path[u - 1]); i <= (depth - u + 1) * b / a; i++) {
		path[u] = i;
		int c = a, d = b;
		jian(&c, &d, i);
		if (c < 0) continue;
		int g = gcd(max(c, d), min(c, d));
		c /= g, d /= g;
		if (dfs(u + 1, c, d)) return true;
	}
	return false;
}
void dfs2 (int u, int a, int b) {
	if (a == 1 && !mp[b] && b < maxn && !mpp[b]) {
		path[u] = b;
		for (int i = 1; i <= depth; i++) 
			ans[i] = path[i];
		maxn = b;
		mp[b] = true;
		return;
	}
	if (u > depth) return;
	for (int i = max(b / a, path[u - 1]); i <= (depth - u + 1) * b / a; i++) {
		if (mpp[i]) continue;
		path[u] = i;
		int c = a, d = b;
		jian(&c, &d, i);
		if (c < 0) continue;
		int g = gcd(max(c, d), min(c, d));
		c /= g, d /= g;
		mpp[i] = true;
		dfs2(u + 1, c, d);
		mpp[i] = false;
	}
}
int main () {
	int a, b;
	cin >> a >> b;
	while (!dfs(1, a, b)) depth++;
	maxn = path[depth];
	mp[maxn] = true;
	dfs2(1, a, b);
	for (int i = 1; i <= depth; i++) cout << ans[i] << " ";
	return 0;
}
2024/1/26 20:55
加载中...