埃及分数90求助
查看原帖
埃及分数90求助
454650
XCH_0803楼主2022/7/22 12:46
#include<bits/stdc++.h>
using namespace std;
const int maxdep=10,maxlongint=2147483647;
int depth;
bool found;
int answer[maxdep],d[maxdep];
int gcd(int a,int b){
	int t=a%b;
	while(t){
		a=b;
		b=t;
		t=a%b;
	}
	return b;
}
void serch(int a,int b,int k){
	int i,m,s,t;
	if(k==depth+1){
		return ;
	}
	else if(b%a==0&&b/a>d[k-1]){
		d[k]=b/a;
		if(!found||d[k]<answer[k]){
			memcpy(answer,d,sizeof(d));
		}
		found=true;
		return ;
	}
	s=max(b/a,d[k-1])+1;
	t=(depth-k+1)*b/a;
	t=min(t,maxlongint/b);
	if(found){
		t=min(t,answer[depth]-1);
	}
	for(i=s;i<=t;i++){
		d[k]=i;
		m=gcd(i*a-b,b*i);
		serch((i*a-b)/m,b*i/m,k+1);
	}
}
int main(){
	int a,b;
	int i;
	found=false;
	d[0]=1;
	cin>>a>>b;
	for(depth=1;depth<=maxdep;depth++){
		serch(a,b,1);
		if(found){
			for(i=1;i<=depth;i++){
				cout<<answer[i]<<" ";
			}
			break;
		}
	}
	return 0;
}
2022/7/22 12:46
加载中...