Subtask #1TLE求调
查看原帖
Subtask #1TLE求调
1181602
Cute_Furina楼主2024/12/1 20:38
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define __gcd gcd
int dep = 1, st[11], ans[11], flag, a, b, c;
int gcd(int x, int y) {
	if(y == 0) return x;
	else return gcd(y, x % y);
}
void dfs(int a, int b, int x) {
	if(x > dep) return ;
	if(a == 1 && b > st[x - 1]) {
		st[x] = b;
		if(!flag || st[x] < ans[x]) {
			for(int i = 1;i <= dep;i ++)
				ans[i] = st[i];
		}
		flag = 1;
		return ;
	}
	int l = max(b / a, st[x - 1] + 1);
	int r = (dep - x + 1) * b / a;
	if(flag && r >= ans[dep]) {
		r = ans[dep] - 1;
	}
	for(int i = l;i < r;i ++) {
		st[x] = i;
		int gc = __gcd(a * i - b, b * i);
		dfs((a * i - b) / gc, b * i / gc, x + 1);
	}
}
signed main() {
	cin >> a >> b;
	c = __gcd(a, b);
	a /= c, b /= c, st[0] = 1;
	for(dep = 1;dep <= 10;dep ++) {
		dfs(a, b, 1);
		if(flag) {
			for(int i = 1;i <= dep;i ++) {
				printf("%lld ", ans[i]);
			}
			break;
		}
	}
	return 0;
}

如果你指出了代码的错误,我会给你一个关注

2024/12/1 20:38
加载中...