UVA12558 Egyptian Fractions (HARD version)

做完了ybt上的那道埃及分数，以为这道题只需要改一下就能过，结果断断续续折腾了一天多，我还是太菜了。

这道题与ybt那道主要区别就是多组数据+给定不能用的数。多组数据容易搞定，但处理不能用的数就把我坑惨了。

我最开始是直接拿bool数组来记录，然后次次本机AC，提交RE，调试发现是越界了。虽然答案不会很大，但由于是从小到大枚举，最开始最后一个就会很大而越界。

然后我就用了个数组，排序后用来判断，然后就WA了，看了题解才发现我并没有给判断最后一个，而很显然最后一次得到的数不一定满足单调性。最后我干脆就直接用set，然而因为忘了clear()又WA了几发才终于A掉了。

ll A,B,cur[1005],ans[1005],mn,k,t,kase,cnt;
set <ll> s;

bool better(int mx)
{
    for(int i=mx;i>=0;i--)
    {
        if(ans[i]==cur[i]) continue;
        return ans[i]==-1 || cur[i]<ans[i]; 
    }
    return 0;
}

ll gcd(ll x,ll y)
{
    return y ? gcd(y,x%y) : x;
}

void dfs(ll x,ll a,ll b,ll n,ll last)
{
    if (x==n)
    {
        if (b%a) return;
        b/=a;
        if (s.count(b)) return;
        cur[x]=b;
        if (better(n))
        {
            mn=b;
            memcpy(ans,cur,sizeof(ll)*(n+1));
        }
        return;
    }
    last++;
    last=max(last,b/a+1);
    for (;last<mn;last++)
    {
        if (a*last>=b*(n-x+1)) break;
        if (s.count(last)) continue;
        cur[x]=last;
        ll g=gcd(a*last-b,b*last);
        dfs(x+1,(a*last-b)/g,(b*last)/g,n,last);
    }
    return;
}

int main()
{
    t=read();
    while (t--)
    {
        s.clear();
        A=read(); B=read(); k=read();
        for (ll i=1;i<=k;i++) s.insert(read());
        printf("Case %lld: %lld/%lld=",++kase,A,B);
        ll i=1;
        for (;;)
        {
            cnt=1; mn=1e18;
            memset(ans,-1,sizeof(ans));
            dfs(1,A,B,i,0);
            if (mn<1e18) break;
            i++;
        }
        for (ll j=1;j<i;j++) printf("1/%lld+",ans[j]);
        printf("1/%lld\n",ans[i]);
    }
    return 0;
}