题意： 古埃及，人们使用单位分数的和(形如1/a的, a是自然数)表示一切有理数。 如：2/3=1/2+1/6,但不允许2/3=1/3+1/3,因为加数中有相同的。 对于一个分数a/b,表示方法有很多种，但是哪种最好呢？ 首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越 好。 如： 19/45=1/3 + 1/12 + 1/180 19/45=1/3 + 1/15 + 1/45 19/45=1/3 + 1/18 + 1/30, 19/45=1/4 + 1/6 + 1/180 19/45=1/5 + 1/6 + 1/18. 最好的是最后一种，因为1/18比1/180,1/45,1/30,1/180都大。 给出a,b(0<a<b<1000),编程计算最好的表达方式。
思路：迭代加深搜索。这道题找了两个oj，结果都wa了…然而看了数据发现自己并没错是oj的数据错了……….改了两天真是心塞……真是坑
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<ctime>
#define eps 1e-6
#define LL long long
#define pii pair<int, int>
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;const int MAXN = 1000000;
//const int INF = 0x3f3f3f3f;
LL a, b;
LL gcd(LL a, LL b) {if(!b) return a;return gcd(b, a%b);
}
LL ans[MAXN], tmp[MAXN];
bool cmp(int d) {for(int i = d; i; i--) if(ans[i] != tmp[i]) return tmp[i] < ans[i];return false;
}
void update(int d) {for(int i = 1; i <= d; i++) ans[i] = tmp[i];
}
bool dfs(int dep, LL st, LL a, LL b, int maxd) {if(dep == maxd) {if(b%a!=0 || b/a<st) return false;tmp[dep] = b / a;//cout << b << " " << a << endl;if(ans[1]==-1 || cmp(maxd)) update(maxd);return true;}st = max(st, (b+a-1)/a);bool tag = 0;for(LL i = st; ; i++) {if((maxd-dep+1)*b <= a*i) break;LL t = a*i - b, div = gcd(t, b*i);LL ta = t / div, tb = b*i / div;tmp[dep] = i;tag |= dfs(dep+1, i+1, ta, tb, maxd);}return tag;
}
int main() {while(cin >> a >> b) {int len;for(int d = 1; ; d++) {for(int i = 1; i <= d; i++) ans[i] = -1;if(dfs(1, (b+a-1)/a, a, b, d)) {len = d;break;}}//printf("%I64d/%I64d=1/%I64d", a, b, ans[1]);cout << ans[1];for(int i = 2; i <= len; i++) printf(" %I64d", ans[i]);puts("");}return 0;
}