UVa-12558 Egyptian Fractions (HARD version)

 1 #include <bits/stdc++.h>
 2 #define _for(i,a,b) for(int i = (a);i < (b);i ++)
 3 #define LL long long int
 4 using namespace std;
 5 
 6 LL maxd;
 7 LL ans[13939],v[13939];
 8 LL lim[9];
 9 
10 LL get_first(LL a,LL b)
11 {
12     return b/a+1;
13 }
14 
15 LL gcd(LL a,LL b)
16 {
17     return (b==0)?a:gcd(b,a%b);
18 }
19 
20 bool better(int d)
21 {
22     for(int i = d;i >= 0;i --)
23         if(v[i]!=ans[i])
24             return ans[i]==-1||v[i]<ans[i];
25     return false;
26 }
27 
28 bool dfs(int d,LL from,LL aa,LL bb)
29 {
30     if(d==maxd)
31     {
32         if(aa!=1) return false;
33         v[d] = bb;
34         int cf = 0;
35         _for(j,0,6)
36             if(v[d]==lim[j]) cf=1;
37         if(cf) return false;
38         if(better(d))
39             memcpy(ans,v,sizeof(LL)*(d+1));
40         return true;
41     }
42     bool ok = false;
43     from =  max(from,get_first(aa,bb));
44     for(int i = from ; ; i ++)
45     {
46         if(bb*(maxd+1-d) <= i*aa) break;
47         int cf = 0;
48         _for(j,0,6)
49             if(i==lim[j]) cf=1;
50         if(cf) continue;
51         v[d] = i;
52         LL b2 = bb*i;
53         LL a2 = aa*i-bb;
54         LL g = gcd(a2,b2);
55         if(dfs(d+1,i+1,a2/g,b2/g)) ok = true;
56     }
57     return ok;
58 }
59 
60 int kase = 1;
61 int main()
62 {
63     int T;
64     scanf("%d",&T);
65     while(T--)
66     {
67         int a,b,k;
68         memset(ans,-1,sizeof(ans));
69         memset(v,0,sizeof(v));
70         memset(lim,0,sizeof(lim));
71         scanf("%d%d%d",&a,&b,&k);
72         _for(i,0,k)
73         {
74             scanf("%d",&lim[i]);
75         }
76         
77         int ok = 0;
78         for(maxd = 1; maxd<10; maxd ++)
79         {
80             if(dfs(0,get_first(a,b),a,b))
81             {
82                 ok = 1;
83                 break;
84             }
85         }
86         printf("Case %d: %lld/%lld=",kase++,a,b);
87         if(ok)
88         {
89             _for(i,0,maxd)
90             printf("1/%lld+",ans[i]);
91         printf("1/%lld
",ans[maxd]);
92         }
93         else    printf("%d/%d
", a, b);
94     }
95     return 0;
96 }