100分TLE,接下来怎样优化
查看原帖
100分TLE,接下来怎样优化
999274
CNS_5t0_0r2楼主2023/9/30 14:18
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 11;
int dep,st[N],ans[N];
int a,b,c;
bool flag;
int read(){
	int x = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9')
		ch = getchar();
	while (ch >= '0' && ch <= '9'){
		x = (x << 3) + (x << 1) + ch - 48;
		ch = getchar();
	}
	return x;
}
int GCD(int x,int y){
	return y ? GCD(y, x % y) : x;
}
void dfs(int a,int b,int x){
	if(x > dep)
		return;
	if(a == 1){
		if(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 - 1) / a,st[x - 1] + 1),r = (dep - x + 1) * b / a;
	if(flag && r >= ans[dep])
		r = ans[dep] - 1;
	for(int i = l;i <= r;i++){
//		if(GCD(b,i) == 1)
//			continue;
		st[x] = i;
		int A = a * i - b,B = b * i;
		int gcd = GCD(A,B);
		dfs(A / gcd,B / gcd,x + 1);
	}
}
signed main(){
	a = read();b = read();
	c = GCD(a,b);
	a /= c;b /= c;
	st[0] = 1;
	for(dep = 1;dep <= N - 1;dep++){
		dfs(a,b,1);
		if(flag){
			for(int i = 1;i <= dep;i++)
				printf("%lld ",ans[i]);
			return 0;
		}
	}
	return 0;
}
2023/9/30 14:18
加载中...