Subtask #1 TLE求调
查看原帖
Subtask #1 TLE求调
1045387
Kobe_BryantQAQ楼主2024/12/14 19:23
#include <bits/stdc++.h>
#define P pair<long long, long long>
#define f(x) x.first
#define s(x) x.second
#define mp(x, y) make_pair(x, y)
using namespace std;
long long n, m, dep, fm[100005], ans[100005], ma = 10000005;
bool vis;
long long gcd(long long a, long long b){
	return (a % b == 0 ? b : gcd(b, a%b));
}
void yf(P &x){
	long long gcd_ = gcd(f(x), s(x));
	f(x) /= gcd_ , s(x) /= gcd_;
}
P operator- (P x, P y){
	long long c = gcd(s(x), s(y));
	P d;
	f(d) = f(x) * s(y) / c - f(y) * s(x) / c, s(d) = s(x) * s(y) / c;
	yf(d);
	return d;
}
P operator/ (P x, long long y){
	P d = x;
	s(d) *= y;
	yf(d);
	return d;
}
bool operator> (P x, P y){
	return f(x) * s(y) > s(x) * f(y);
}
void dfs(int step, P x){
	yf(x);
	if(step == dep){
		if(f(x) == 1 && s(x) < ma && s(x) > fm[step - 1]){
			ma = s(x);
			vis = 1;
			for(int i = 1; i < step; i ++){
				ans[i] = fm[i];
			}
			ans[step] = s(x);
		} 
		return ;
	}
	long long k = fm[step - 1] + 1;
	P pj = x / (dep - step + 1);
	while(mp(1, k) > x){
		k ++;
	}
	for(; mp(1, k) > pj; k ++){
		fm[step] = k;
		dfs(step + 1, x - mp(1, k));
	}
}
int main() {
	cin >> n >> m;
	P x = mp(n, m);
	yf(x);
	if(f(x) == 1){
		cout << s(x);
		return 0;
	}
	for(dep = 1; ; dep ++){
		fm[0] = 1;
		dfs(1, x);
		if(vis){
			for(int i = 1; i <= dep; i ++){
				cout << ans[i] << ' ';
			}
			return 0;
		}
	}
	return 0;
}

大佬们请问是剪枝没剪够吗QAQ

2024/12/14 19:23
加载中...