信息学奥赛一本通T1444：埃及分数

【题目描述】

在古埃及，人们使用单位分数的和(形如1/a的, a是自然数)表示一切有理数。如：2/3=1/2+1/6,但不允许2/3=1/3+1/3,因为加数中有相同的。对于一个分数a/b,表示方法有很多种，但是哪种最好呢？首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越好。

如：19/45=1/3 + 1/12 + 1/180

19/45=1/3 + 1/15 + 1/45

19/45=1/3 + 1/18 + 1/30,

19/45=1/4 + 1/6 + 1/180

19/45=1/5 + 1/6 + 1/18.

最好的是最后一种，因为1/18比1/180,1/45,1/30,1/180都大。

给出a,b(0＜a＜b＜1000),编程计算最好的表达方式。

【输入】

输入：a b

【输出】

若干个数，自小到大排列，依次是单位分数的分母。

【输入样例】

19 45

【输出样例】

5 6 18

【源程序】

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define EPS 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
const int MOD = 1E9+7;
const int N = 200+5;
const int dx[] = {-1,1,0,0,-1,-1,1,1};
const int dy[] = {0,0,-1,1,-1,1,-1,1};
using namespace std;

LL maxDeep;
LL temp[N];
LL res[N];
LL GCD(LL a,LL b){
    return b==0?a:GCD(b,a%b);
}
bool judge(LL step){//当最小分数分母比原来大进行更新
    if(res[step]==-1)
        return true;
    else if(temp[step]>res[step])
        return false;
    else if(temp[step]<res[step])
        return true;
    else
        return false;
}
LL getLimit(LL x,LL y){
    for(LL i=2;;i++)
        if(y<x*i)// 1/i<=x/y
            return i;
}
bool dfs(LL step,LL minn,LL x,LL y){
	if(step==maxDeep){
		if(y%x)
            return false;
        else{
            temp[step]=y/x;
            if(judge(step))//存在更优解，更新答案
                memcpy(res,temp,sizeof(temp));
            return true;
        }
	}
	minn=max(minn,getLimit(x,y));//取得新下界，注意这里取的是max（分母），以防止漏除枚举。

	bool flag=false;
	for(LL i=minn;;i++){
		if((maxDeep-step+1)*y<=x*i)//剪枝，(maxDeep-step+1)*(1/i)<=x/y
            break;

		temp[step]=i;
		LL ny=y*i;
		LL nx=x*i-y;

		LL gcd=GCD(nx,ny);
		if(dfs(step+1,minn+1,nx/gcd,ny/gcd))
            flag=true;
	}
	return flag;
}
int main(){
    LL n,m;
    scanf("%lld%lld",&n,&m);
	for(maxDeep=1;;maxDeep++){
		LL limit=getLimit(n,m);
		memset(temp,0,sizeof(temp));
		memset(res,-1,sizeof(res));
		if(dfs(0,limit,n,m))//找到第一个可行解即退出
            break;
	}
	for(LL i=0;i<=maxDeep;i++)
        printf("%lld ",res[i]);
	return 0;
}

信息学奥赛一本通T1444：深搜的剪枝技巧 埃及分数 归属于 深搜的剪枝技巧，更多同类题解源程序见：深搜的剪枝技巧 和 埃及分数