UVA12558 埃及分数 Egyptian Fractions (HARD version)

#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;
}

UVA12558 埃及分数 Egyptian Fractions (HARD version)

原文：https://www.cnblogs.com/pelom/p/10576211.html