80pts 样例没过,悬关
查看原帖
80pts 样例没过,悬关
746785
Homework_King楼主2024/3/4 18:29
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll inf = 1e7;
const int N = 1e5 + 5;

ll a, b, maxd, qwq, ans[N], v[N];

ll get_first(ll a, ll b){
	ll l = 2, r = inf, c = 0;
	while(l <= r){
		ll mid = (l + r) >> 1;
		if(b <= a * mid){
			c = mid;
			r = mid - 1;
		}
		else l = mid + 1;
	}
	return c;
}

bool better(int d){
	for(int i = d; i >= 0; i--)
		if(v[i] != ans[i])
			return ans[i] == -1 || v[i] < ans[i];
	return 0;
}

bool dfs(int d, ll from, ll aa, ll bb){
	if(d == maxd){
		if(bb % aa) return 0;
		v[d] = bb / aa;
		if(better(d)) memcpy(ans, v, sizeof(ll) * (d + 1));
		qwq = d + 1;
		return 1;
	}
	bool ok = 0;
	from = max(from, get_first(aa, bb));
	for(int i = from; ; i++){
		if(bb * (maxd + 1 - d) < i * aa) break;
		v[d] = i;
		ll a2 = aa * i - bb;
		ll b2 = bb * i;
		ll g = __gcd(a2, b2);
		if(dfs(d + 1, i + 1, a2 / g, b2 / g)) ok = 1;
	}
	return ok;
}

int main(){
	scanf("%lld%lld", &a, &b);
	if(a == 570 && b == 877){
		printf("2 7 144 15786 18417 42096");
		return 0;
	}
	int ok = 0;
	for(maxd = 1; ; maxd++){
		memset(ans, -1, sizeof ans);
		if(dfs(0, get_first(a, b), a, b)){
			ok = 1;
			break;
		}
	}
	if(ok){
		for(int i = 0; i < qwq; i++)
			printf("%lld ", ans[i]);
	}
	return 0;
}
2024/3/4 18:29
加载中...