题意：
经典的埃及分数问题，即给出一个真分数，求出用个数最少的单位分数来表示这个分数。如果有多种方案，要让每个分数尽量的大，即分母尽量的小。会有K个禁止使用的单位分数。
分析：
IDA*算法。当按照分母递增的顺序排列时， 如果当前考虑的分数为1/e，剩下的maxd - d+1层都是1/e,但仍然到不了目标的a/b的时候，就剪枝。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
const int maxn=10010;
int t;
ll n,m,k;
ll ans[maxn],v[maxn];
set<ll>del;
ll getfirst(ll a,ll b)
{
ll c=(b/a)+1;
return c;
}
bool better(int d)
{
for(int i=d;i>=0;i--)
{
if(v[i]!=ans[i])
return (ans[i]==-1||v[i]<ans[i]);
}
return false;
}
ll gcd(ll a,ll b)
{
return b?gcd(b,a%b):a;
}
bool dfs(ll a,ll b,ll start,int d,int maxd)
{
if(d==maxd)
{
//cout<<maxd<<endl;
if(b%a)
return false;
v[d]=b/a;
if(del.count(b/a))
return false;
if(better(d))
memcpy(ans,v,sizeof(ll)*(d+1));
return true;
}
bool ok=false;
for(ll i=max(start,getfirst(a,b));;++i)
{
//cout<<i<<endl
if(b*(maxd+1-d)<=i*a)
break;
if(del.count(i))
continue;
v[d]=i;
ll b1=b*i;
ll a1=a*i-b;
ll g=gcd(a1,b1);
if(dfs(a1/g,b1/g,i+1,d+1,maxd))
ok=true;
}
return ok;
}
int main()
{
scanf("%d",&t);
for(int cas=1;cas<=t;cas++)
{
del.clear();
scanf("%lld%lld%lld",&n,&m,&k);
int i,j;
ll del0;
while(k--)
{
scanf("%lld",&del0);
del.insert(del0);
}
int maxd;
for(maxd=0;;maxd++)
{
//cout<<maxd<<endl;
memset(ans,-1,sizeof(ans));
if(dfs(n,m,getfirst(n,m),0,maxd))
break;
}
printf("Case %d: %lld/%lld=",cas,n,m);
for(i=0;i<=maxd;++i){
if(i) printf("+");
printf("1/%lld",ans[i]);
}
printf(" ");
}
}