codevs 1288 埃及分数

1288 埃及分数

迭代加深搜索+剪枝
 1 #include<cmath>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 using namespace std;
 7 #define N 1000000+15
 8 #define LL long long
 9 LL n,x,y;
10 LL ans[N],num[N];
11 bool if_;
12 
13 inline void read(LL &now)
14 {
15     char ch=getchar(); now=0;
16     while(ch>'9'||ch<'0') ch=getchar();
17     while(ch>='0'&&ch<='9') now=now*10+ch-'0',ch=getchar();
18 }
19 
20 int gcd(LL a,LL b) { return !b?a:gcd(b,a%b); }
21 
22 void dfs(LL step,LL from,LL m,LL d)
23 {
24     if(step<0)return;
25     if(d==1){
26         if(step==1&&from>=m)
27         {
28             if(from<num[1])
29             {
30                 if_=true;
31                 num[1]=from;
32                 for(int i=n;i>=2;i--)
33                     num[i]=ans[i];
34             }
35         }
36         return ;
37     }
38     for(LL i=m; ;i++)
39     {
40         ans[d]=i;
41         LL g=gcd(step*i-from,from*i);
42         dfs((step*i-from)/g,from*i/g,i+1,d-1);
43         if(step*i>from*d) break;
44     }
45 }
46 
47 int main()
48 {
49     read(x); read(y);
50     num[1]=0x7f7f7f7f;
51     for(int i=1;;i++)
52     {
53         n=i,dfs(x,y,1,i);
54         if(if_)
55         {
56             for(int i=n;i;i--) printf("%lld ",num[i]);
57             return 0;
58         }
59     }
60     return 0;
61 }
View Code