UVa 12558 - Egyptian Fractions (HARD version)

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<set>
 5 using namespace std;
 6 typedef  long long LL;
 7 LL ans[10002],v[1002];
 8 set<LL> s;
 9 int maxd;
10 LL gcd(LL a,LL b)
11 {
12     return b?gcd(b,a%b):a;
13 }
14 typedef long long LL;
15 LL get_first(LL a,LL b)
16 {
17     return b/a+1;
18 }
19 bool better(int d)
20 {
21     for(int i=d;i>=0;i--)
22         if(v[i]!=ans[i])
23            return ans[i]==-1||v[i]<ans[i];
24     return false;
25 }
26 bool dfs(int d,LL from,LL aa,LL bb)
27 {
28     if(d==maxd)
29     {
30         if(bb%aa) return false;
31         v[d]=bb/aa;
32         if(s.count(bb/aa)) return false;
33 
34         if(better(d)) memcpy(ans,v,sizeof(LL)*(d+1));
35         return true;
36     }
37     bool ok=false;
38     for(LL i=max(from,get_first(aa,bb));;i++)
39     {
40         if(bb*(maxd+1-d)<=i*aa)
41            break;
42         if(s.count(i)) continue;
43         v[d]=i;
44         LL b2=bb*i;
45         LL a2=aa*i-bb;
46         LL g=gcd(a2,b2);
47         if(dfs(d+1,i+1,a2/g,b2/g))
48             ok=true;
49     }
50     return ok;
51 }
52 int main()
53 {
54     int t,k;
55     LL a,b,num;
56     scanf("%d",&t);
57     for(int ii=1;ii<=t;ii++)
58     {
59         s.clear();
60         scanf("%lld%lld%d",&a,&b,&k);
61         for(int i=0;i<k;i++)
62         {
63             scanf("%lld",&num);
64             s.insert(num);
65         }
66         int ok=0;
67         for(maxd=1;;maxd++)
68         {
69             memset(ans,-1,sizeof(ans));
70             if(dfs(0,get_first(a,b),a,b))
71             {
72                 ok=1;break;
73             }
74 
75         }
76         printf("Case %d: %lld/%lld=",ii,a,b);
77         for(int i=0;i<=maxd;++i){
78             if(i) printf("+");
79             printf("1/%lld",ans[i]);
80         }
81         printf("\n");
82     }
83     return 0;
84 }