1444：埃及分数
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
在古埃及，人们使用单位分数的和(形如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),编程计算最好的表达方式。
【输入】
输入：a b
【输出】
若干个数，自小到大排列，依次是单位分数的分母。
【输入样例】
19 45
【输出样例】
5 6 18
解析，深度优先搜索，详见代码：
#include <bits/stdc++.h>
using namespace std;
long long a, b;
long long c[105];
long long ans[105];
int minn;
long long gcd(long long x, long long y) {//求最大公约数
if (x % y == 0) return y;
return gcd(y, x % y);
}
//深搜，step步骤，x剩余分子，y剩余分母，mi当前步骤最小分子
bool dfs(int step, long long x, long long y, int mi) {
if (step == minn && x != 1) return false;//超过最小步骤，且当前步骤无解
if (x == 1) {//有解
c[step] = y;
if (c[step] < ans[step]||ans[step]==0) {//最后一个分子小或者之前无解
for(int i = 1; i <= step; i++) {//保存答案
ans[i] = c[i];
}
}
return true;
}
bool flag=false;
for(int i = mi;; i++) {//枚举当前步骤分子
if (i * x > y) {//比分数小
//剩下的都用当前最小的分子也不够用
if ((minn - step + 1)*y <= x * i) break;
c[step] = i;
//计算差
long long xx = x * i - y;
long long yy = y * i;
long long d = gcd(xx, yy);
xx /= d;
yy /= d;
if (dfs(step + 1, xx, yy, i + 1)) flag=true;//继续深搜
}
}
return flag;
}
int main() {
cin >> a >> b;
minn = 1e9;
for (minn=1;;minn++){//枚举最小步骤
if(dfs(1, a, b, 2)) break;//找到答案就退出循环
}
for(int i = 1; i <= minn; i++) {//输出答案
cout << ans[i] << " ";
}
return 0;
}
