UVA12558 Egyptian Fractions (HARD version)
迭代加深搜索，适用于无上界的搜索。每次在一个限定范围中搜索，如果无解再进一步扩大查找范围。
本题中没有分数个数和分母的上限，只用爆搜绝对TLE。故只能用迭代加深搜索。
#include<cstdio> #include<cstring> #include<set> using namespace std; typedef long long ll; int num,T,t,k; ll h[100001],ans[100001],a,b,q; set <ll> del; //存储不能用的数 bool ok; inline ll gcd(ll A,ll B) {return B ? gcd(B,A%B):A;} inline bool better(){ //判断最优解 for(int i=num;i>=0;--i) if(h[i]!=ans[i]) return ans[i]==-1||h[i]<ans[i]; return 0; } inline void dfs(ll p1,ll p2,int last,int cnt){//p1/p2：分子/分母 last:这次从哪个分母开始搜 cnt:已经添加了几个子分数 if(cnt==num){ if(p2%p1||del.count(p2/p1)) return ; //分子不为1或者这个数被禁止出现 h[cnt]=p2; ok=1; if(better()) memcpy(ans,h,sizeof(ll)*(cnt+1)); //更新最优解 return ; } for(ll i= last>p2/p1+1 ? last:p2/p1+1;;++i) // p2/p1+1:符合条件的最小分母，用于剪枝 { if(p1*i>=p2*(num-cnt+1)) break; //发现最后减不完了，跳出 if(del.count(i)) continue; ll q1=p1*i-p2,q2=p2*i,G=gcd(q1,q2); //通分 h[cnt]=i; dfs(q1/G,q2/G,i+1,cnt+1); } } int main(){ scanf("%d",&T); for(t=1;t<=T;++t){ del.clear(); ok=0; scanf("%lld%lld%d",&a,&b,&k); for(int i=1;i<=k;++i) scanf("%lld",&q),del.insert(q); for(num=1;!ok;++num){ //限定范围 memset(ans,-1,sizeof(ans)); dfs(a,b,b/a+1,0); //b/a+1同上p2/p1+1 }--num; //注意要减掉多出的一次++num操作 printf("Case %d: %lld/%lld=",t,a,b); for(int i=0;i<num;++i) printf("1/%lld+",ans[i]); printf("1/%lld ",ans[num]); } return 0; }