1025 - 搜索優化之迭代加深 - 埃及分數

埃及分數

描述

任何一個分數都能才成若干個單位分數(形如1/a的, a是自然數)的和。
對於一個分數a/b,表示方法有很多種，但是哪種最好呢？
首先，加數少的比加數多的好，其次，加數個數相同的，最小的分數越大越好，如果還是相同，那麼第二小的分數越大越好，依次類推下去。
例如對於19/45，下列方法都是合法的

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

分析

所謂迭代加深，其實就是限制深度的dfs
每次確定一個dfs的深度
而對於這道題：

全局long long真好用

代碼

#include<bits/stdc++.h>
#define re register
#define N 100000
#define int long long
using namespace std;
int a,b,ans[N],tmp[N];
int get(int x,int y){return y/x+1;}
int gcd(int x,int y){
	int z=x%y;
	while(z){x=y;y=z;z=x%y;}
	return y;
}
bool better(int len){
	for(int i=len;i>=0;--i)
		if(ans[i]!=tmp[i])
			return ans[i]==-1||tmp[i]<ans[i];
	return false;
}
bool dfs(int limit,int d,int from,int x,int y){
	if(d==limit){
		if(y%x) return false;
		tmp[d]=y/x;
		if(better(d)) memcpy(ans,tmp,sizeof(tmp));
		return true;
	}
	int flag=0;
	from=max(from,get(x,y));
	for(int i=from;;i++){
		if(1ll*y*(limit-d+1)<=1ll*x*i) break;
		int xx,yy;
		tmp[d]=i;
		xx=1ll*x*i-y;
		yy=y*i;
		int gd=gcd(xx,yy);
		if((dfs(limit,d+1,i+1,xx/gd,yy/gd))) flag=1;
	}
	return flag;
}
signed main(){
	cin>>a;cin>>b;
	int sta=get(a,b),i,j;
	for(i=1;;i++){
		memset(ans,-1,sizeof(ans));
		if(dfs(i,0,sta,a,b))		break;
	}
	for(j=0;j<=i;++j) cout<<ans[j]<<' ';
	return 0;
}