hack tle求调
查看原帖
hack tle求调
940317
lightme楼主2024/1/12 23:00
// Problem: 
//     P1763 埃及分数
//   
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1763
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<iostream>
#include<algorithm>
//#include<cstdio>
#include<cstring>
#define endl '\n'
#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(a);i>(b);i--)
#define N 1000100 //1e6+100 
using namespace std;
int n,m,dep,now[N],ans[N];
bool flag;
void dfs(int a,int b,int d){//a分子 b//分母
	if(d==dep){//判断当前深度已到
		if(a==1&&b>now[d-1]){//当前分数小于前一个分数
			now[d]=b;//符合要求记录
			if(ans[d]>now[d]){//如果最后一位比原来最后一位要小就记录那个最优的
				for(int i=1;i<=d;i++)
					ans[i]=now[i];
			}
			flag=true;//找到答案了,本层完全找完,就推出后面的循环
		}	
		return;
	}
	int low=max(now[d-1]+1,b/a+1);//取的位数一定比取完要小一位
	int up=1e7;
	up=min(up,(dep-d+1)*b/a);//a/b/(dep-d+1)实为每一份最小是,倒数即为分母最大是
	for(int i=low ;i<=up;i++){
		now[d]=i;
		int x=a*i-b,y=b*i;
		int g=__gcd(x,y);
		dfs(x/g,y/g,d+1);
	}
}
signed main(){
	//ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	memset(ans,0x3f,sizeof ans);
	cin>>n>>m;
	//if (n == 570 && m == 877) { printf("2 7 144 15786 18417 42096"); return 0; }
	now[0]=1;
	for(dep=1;!flag;dep++){
		dfs(n,m,1);
	}
	for(int i=1;i<dep;i++){
		cout<<ans[i]<<" ";
	}
	return 0; 
} 


2024/1/12 23:00
加载中...