开O2全re,不开90pts,tle两个点
查看原帖
开O2全re,不开90pts,tle两个点
1019606
KouMoSir楼主2023/10/24 17:36
#include<iostream>
using namespace std;
typedef long long ll;
ll a, b, constr = 1, pre[15], ans[15];
ll gcd(ll x, ll y) {
	ll tmp = x % y;
	if (tmp == 0)return y;
	else gcd(y, x % y);
}
void dfs(ll fenzi, ll fenmu, ll lay) {
	if (lay > constr)return;
	if (pre[lay - 1] > ans[constr])return;
	ll x = fenmu / fenzi, y = (fenmu / fenzi) * (constr - lay + 1);
	if (x * fenzi != fenmu)x += 1;
	x = max(pre[lay - 1] + 1, x);
	for (int i = x; i <= y; i++) {
		ll tmplow = i * fenmu, tmpup = fenzi * i - fenmu;
		pre[lay] = i;
		if (tmpup == 0) {
			if (i < ans[constr])
				for (int i = 1; i <= constr; i++)ans[i] = pre[i];
			return;
		}
		else {
			ll tmp = gcd(tmplow, tmpup);
			tmplow /= tmp, tmpup /= tmp;
			dfs(tmpup, tmplow, lay + 1);
		}
	}
}
int main() {
	cin >> a >> b;
	for (; constr <= 10; constr++) {
		ans[constr] = 0x7ffffffff;
		dfs(a, b, 1);
		if (ans[constr] != 0x7ffffffff) {
			for (int i = 1; i <= constr; i++)cout << ans[i] << " ";
			break;
		}
	}
}
2023/10/24 17:36
加载中...