埃及分数 Hack TLE,该减掉的感觉都剪掉了
查看原帖
埃及分数 Hack TLE,该减掉的感觉都剪掉了
1066579
XP3301_Pipi楼主2024/3/15 21:07

rt。。。
只要对代码有帮助的都会关注 感谢大佬

#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
#define pll pair<ll,ll>
#define int long long
using namespace std;
const int N=8e5+15;
const long long INF=0x3f3f3f3f3f3f3f3fll;

inline void FileIO(){
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
}

template<typename Type>
inline void read(Type& res){
	Type x=0,f=1; char c=' '; while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
	res=x*f;
}

int x,y,cnt,bound,ans[N],num[N],Pow[N];
bool flag; 

void Reduce(int &a,int &b){
	int g=__gcd(a,b);
	a/=g,b/=g;
}

void PrintAns(){
	for(int i=1;i<=cnt;i++) printf("%lld ",ans[i]);
}

void dfs(int step,int a,int b){
	if(step==cnt){
		if(a==1&&b<ans[cnt]&&b>num[step-1]&&b<=bound){
			num[cnt]=b;
			for(int i=1;i<=cnt;i++) ans[i]=num[i];
			return;
		}
	}
	if(step==cnt-1){
		int lz=4*b/a/a+1,rz=min(2*bound/a,bound*bound/b);
		for(int z=lz;z<=rz;z++){
			int delta=a*a*z*z-4*b*z;
			int tmp=sqrt(delta);
			if(tmp*tmp!=delta) continue;
			if(delta%2!=a*z%2) continue;
			num[cnt-1]=(a*z-tmp)/2;
			num[cnt]=(a*z+tmp)/2;
			if(num[cnt]<ans[cnt]){
				for(int i=1;i<=cnt;i++) ans[i]=num[i];
				return;
			}
		}
	}
	if(a==0) return;
	if(a>(cnt-step+1)*Pow[cnt-step]) return;
	if(b>Pow[cnt-step+1]) return;
	int lbound=max(max(num[step-1]+1,bound*b/(bound*a-(cnt-step)*b)),(int)((b*1.0)/a+0.5));
	int rbound=min(bound,b*(cnt-step+1)/a);
	if(lbound>ans[cnt]) return;
	for(int i=lbound;i<=rbound;i++){
		int resa=a*i-b,resb=b*i;
		if(resa<0||resb<0) continue;
		Reduce(resa,resb);
		num[step]=i;
	//	printf("%d/%d-%d/%d=%d/%d\n",a,b,1,i,resa,resb);
		dfs(step+1,resa,resb);
	//	if(flag) return;
	}
}

signed main(){
//	不开longlong见祖宗!
//	检查数组大小!
//	禁止在int乘int时不开longlong!
//	STL数据类型拷贝赋值时间复杂度是 O(N)!
//	freopen("Fraction.out","w",stdout);
	memset(ans,0x3f,sizeof(ans));
	read(x),read(y);
	Reduce(x,y);
//	printf("%d/%d\n",x,y);
	Pow[0]=1;
	for(cnt=2;cnt<=10000000;cnt++){
		for(bound=100;bound<=10000000;bound*=10){
//			printf("Cnt=%d,Bound=%d\n",cnt,bound);
//			for(int i=1;i<=30;i++) puts("HAHAHAHAHHAHAHAHAHAHAHAHAHHAHAHAHAHAHAHAHHAHAHAHAHAHAHAHAHAHHAHA");
			for(int i=1;i<=100;i++){
				Pow[i]=Pow[i-1]*bound;
				if(Pow[i]>1e15)
					Pow[i]=1e15;
			}
			dfs(1,x,y);
			if(ans[cnt]<=10000000+114514){
				PrintAns();
				return 0;
			}
		}
	}
	return 0;
}







2024/3/15 21:07
加载中...