TLE Subtask#1求调
查看原帖
TLE Subtask#1求调
816204
Light_LE楼主2025/1/16 22:20
#include <bits/stdc++.h>
#define fin cin
#define fout cout

#define maxn 66
using namespace std;
long long st[maxn], ans[maxn], flag;
void iddfs(long long a, long long b, int dep, int maxdep) {
	if (dep > maxdep) {
		return;
	}
	
	if (a == 1 && b > st[dep - 1]) {// 剩下 1/b ,找到了答案
		st[dep] = b;
		if (flag == 0 || st[dep] < ans[dep]) {// 答案更优 
			for (int i = 1; i <= dep; i++) {
				ans[i] = st[i];
			}
			flag = 1;
			return;
		}
	}
	
	long long l = max(b / a, st[dep - 1] + 1);// 从上一个,或者 b/a 开始枚举
	long long r = (maxdep - dep + 1) * b / a;// 枚举上限最优性剪枝
	if (flag && r >= ans[maxdep]) {
		r = ans[maxdep] - 1;
	}
	for (long long i = l; i < r; i++) {
		st[dep] = i;
		long long gc = __gcd(a * i - b, b * i);
		iddfs((a * i - b) / gc, b * i / gc, dep + 1, maxdep);
	}
}
int main() {
	//ifstream fin("light.in");
	//ofstream fout("light.out");
	ios::sync_with_stdio(0); fin.tie(0); fout.tie(0);
	
	long long a, b;
	fin >> a >> b;
	long long c = __gcd(a, b);
	a /= c, b /= c, st[0] = 1;
	for (int dep = 1; dep <= 10; dep++) {
		iddfs(a, b, 1, dep);
		if (flag) {
			for (int i = 1; i <= dep; i++) {
				cout << ans[i] << " ";
			}
			break;
		}
	}
	return 0;
}
2025/1/16 22:20
加载中...