问题描述

在古埃及，人们使用单位分数的和（形如 ${\frac{1}{a}}$ 的，a 是自然数）表示一切有理数。

如：$\frac{2}{3}= \frac{1}{2}+ \frac{1}{6}$，但不允许 $\frac{2}{3}= \frac{1}{3}+ \frac{1}{3}$，因为加数中有相同的。

对于一个分数 ab，表示方法有很多种，但是哪种最好呢？

首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越好。如：

$\frac{19}{45}=\frac{1}{3}+\frac{1}{12}+\frac{1}{180}。$
$\frac{19}{45}=\frac{1}{3}+\frac{1}{15}+\frac{1}{45}。$
$\frac{19}{45}=\frac{1}{3}+\frac{1}{18}+\frac{1}{30}。$
$\frac{19}{45}=\frac{1}{4}+\frac{1}{6}+\frac{1}{180}。$
$\frac{19}{45}=\frac{1}{5}+\frac{1}{6}+\frac{1}{18}。$

最好的是最后一种，因为 $\frac{1}{18}$ 比 $\frac{1}{180}，\frac{1}{45}，\frac{1}{30}，\frac{1}{180}$ 都大。
给出 a,b，编程计算最好的表达方式。

方法一 贪心(只能求出可行解但不一定是最优解)(贪心只能找到可行解，长度也不一定最短，不能AC，下面的解法可以AC)

贪心策略: 对于目标$\frac{a}{b}$，每次寻找小于其的最大埃及分数$\frac{1}{c}$,新的目标转换为$\frac{a}{b} - \frac{1}{c} = \frac{ac-b}{bc}$,再递归求解即可
递归终点: 对于某次的$\frac{a}{b}$若b%a == 0即可以转换成一个埃及分数，则递归结束。
算法流程:

• 寻找最大的$\frac{1}{c}$,即是寻找最小的$c = \lfloor\frac{b}{a}\rfloor+1$
• 寻找新的目标分数: $\frac{ac-b}{bc} =\frac{a(\lfloor\frac{b}{a}\rfloor+1)-b}{bc}=\frac{a-b \% a}{bc}$
• 以最简形式递归求解，设$d = gcd(a-b \% a, bc)$,则$find((a-b \% a)/d, bc/d)$

c++代码实现

#include <iostream>
using namespace std;

typedef long long LL;//分母可能很大，乘法后可能会爆int 
const int N = 1010;
LL ans[N];//记录埃及分数的分母 
LL a, b;
int cnt;//ans数组的大小 
//欧几里得 
LL gcd(LL x, LL y) {
    return y == 0? x : gcd(y, x%y);
}

void find(LL a, LL b) {
    //递归终点
    if(a == 1) {
        ans[cnt++] = b;
        return ;
    }
    //寻找下一次求解的目标 
    LL c = b/a+1;
    ans[cnt++] = c;
    a = a-b%a;
    b = b*c;
    //最简形式递归求解 
    LL t = gcd(a, b);
    find(a/t, b/t);
}

int main() {
    cin>>a>>b;
    find(a, b);
    for(int i = 0; i < cnt; ++i){
        cout<<ans[i]<<" ";
    }
    cout<<endl;
    return 0;
}

方法二 IDA*(可求解出最优解)

上面的贪心做法只能找到可行解但是不一定能找到最优解，若要寻找长度最短且最小分数最大的最优方案，可以考虑搜索出加数最少的所有情况，找到最优解。
首先考虑朴素做法，对所有的数字进行dfs或者bfs，但是dfs深度没有上限，随时可能爆栈，bfs宽度也无上限，连第一层都扩展不完，于是尝试优化。
迭代加深
既然深搜深度不定，并且我们要求的是加数最短的情况，可以从小到大枚举dfs的深度上限，每次dfs只尝试深度不超出maxd的节点。(这种做法其实就是迭代加深搜索。)
利用估计函数剪枝
这样解决的深度无限的问题，但是直接迭代加深搜索还是可能超时，于是需要进行剪枝。
既然每次搜索的深度上限固定，我们可以算出哪些分支在限度之内不可能找到答案。假设枚举到第$deep$层时已经计算的分数为:$\frac{c}{d}$目标分数为$\frac{a}{b}$,小于$\frac{a}{b} -\frac{c}{d}$的最大埃及分数为$\frac{1}{e}$，则至少需要$need = \frac{\frac{a}{b} -\frac{c}{d}}{\frac{1}{e}}$层搜索才能出结果，所以我们可以剪去所有的$deep+need > maxd$的分支。(这样在迭代加深搜索中加入估计函数的算法就是IDA*算法)。

算法流程：

• 枚举搜索的最大深度maxd
• 找到第一个可行的maxd,其所有解中的最优解就是最终答案
• 输出结果

dfs过程

• 递归终点：当前深度达到maxd:

  若$\frac{a}{b}$是埃及分数，即当前解是可行解，尝试更新ans，
  若$\frac{a}{b}$不是埃及分数，即当前不是可行解，直接退出。

• 枚举下一层的起始数，直到不可能在maxd步数内完成为止。

C++代码实现

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int maxd;
typedef long long LL;
const int N = 1000;
int ans[N], temp[N];//ans为总体最优解，temp为某次搜索的解
//比较temp是否优于ans,temp更优返回true
bool cmp(int d) {
    if(!ans[d]) return true;
    return temp[d] < ans[d];
}
//获取小于a/b最大的1/x的分母x
LL get_first(LL a, LL b) {
    return b/a+1;
}
//求最大公因数
LL gcd(LL a, LL b) {
    return b==0 ? a : gcd(b, a%b);
}

//四个参数：d:递归深度，last:当前可选择的最小的分母, 目标:分解a/b
bool dfs(int d, LL last, LL a, LL b){
    if(d == maxd) {
        if(b % a || b > 1e7) {//最后一个数不是埃及分数,无解
            return false;
        }
        //找到可行解
        temp[d] = b/a;
        if(temp[d] <= temp[d - 1]) return false;
        if(cmp(d)) {
            memcpy(ans, temp, sizeof ans);
        }
        return true;
    }
    bool flag = false;
    last = max(last, get_first(a, b));
    for(int i = last; ;i++) {
        //利用估价函数剪枝
        //若后面全是1/i再(maxd+1-d)步数内也达不到a/b则剪掉
        if(b*(maxd+1-d) <= i*a) {
            break;
        }
        temp[d] = i;
        //继续进行下一层搜索
        //a/b - 1/i的结果
        LL a1 = a*i-b;
        LL b1 = b*i;
        LL t = gcd(a1, b1);
        if(dfs(d+1, i+1, a1/t, b1/t)){
            flag = true;
        }
    }
    return flag;
}

int main() {
    LL a, b;
    cin>>a>>b;
    LL d = gcd(a, b);
    a /= d;
    b /= d;
//     if(a == 1) {
//         printf("%d\n", b);
//         return 0; 
//     }

    for(maxd = 1; ; maxd++){
        if(dfs(0, get_first(a, b), a, b)){
            break;
        }
    }
    for(int i = 0; i <= maxd; ++i) {
        printf("%d ", ans[i]);
    }
    return 0;
}