UVA12558 埃及分数

#include<iostream>

#include<cstdio>

#include<set>

#include<memory.h>

using namespace std;

#define int long long

#define max(a,b) ((a)>(b)?(a):(b))

#define N 1000010

set<int> S;

int T,a,b,n;

int d;

int r[N],ans[N],v[N];

bool op;

int gcd(int x,int y){

    return y?gcd(y,x%y):x;

}

inline bool compare(int x){

    for(int i=x;i>=1;i--)

        if(r[i]!=ans[i])

            return ans[i]==-1 || r[i]<ans[i];

    return 0;

}

void dfs(int k,int t,int p,int q){

    if(k==d){

        if(p!=1 || S.count(q))

            return ;

        r[k]=q;

        if(compare(d))

            for(int i=1;i<=d;i++)

                ans[i]=r[i];

        op=1;

        return ;

    }

    t=max(t,(q-1)/p+1);

    for(;;t++){

        if(q*(d-k+1)<=t*p)

            break;

        if(S.count(t))

            continue;

        r[k]=t;

        int np=p*t-q,nq=q*t,nr=gcd(np,nq);

        dfs(k+1,t+1,np/nr,nq/nr);

    }

}

signed main(){

    scanf("%d",&T);

    for(int i=1;i<=T;i++){

        op=0;

        S.clear();

        scanf("%lld%lld%lld",&a,&b,&n);

        printf("Case %lld: %lld/%lld=",i,a,b);

        int x;

        for(int j=1;j<=n;j++){

            scanf("%lld",&x);

            S.insert(x);

        }

        for(d=1;;d++){

            memset(ans,-1,sizeof(ans));

            dfs(1,0,a,b);

            if(op)

               break;

            }

        for(int j=1;j<d;j++)

            printf("1/%lld+",ans[j]);

        printf("1/%lld\n",ans[d]);

    }

    return 0;

}