埃及分数（Eg[y]ptian Fractions (HARD version), Rujia Liu's Present 6, UVa12558）

把a/b写成不同的埃及分数之和，要求项数尽量小，在此前提下最小的分数尽量大，然后第二小的分数尽量大……另外有k（0≤k≤5）个数不能用作分母。例如，k=0时\(5/121=1/33+1/121+1/363\)，不能使用33时最优解为\(5/121=1/45+1/55+1/1089\)。输入保证\(2≤a<b≤876，gcd(a,b)=1\)，且会挑选比较容易求解的数据。

输入输出

第一行输入是T，下面T行每行是一组输入示例，每行的前三个数是a,b,k。之后的k个数是不能用作分母的k个数。

Sample Input
5
2  3  0
19  45  0
2  3  1  2
5  121  0
5  121  1  3

Sample Output
Case  1:  2/3=1/2+1/6
Case  2:  19/45=1/5+1/6+1/18
Case  3:  2/3=1/3+1/4+1/12
Case  4:  5/121=1/33+1/121+1/363
Case  5:  5/121=1/45+1/55+1/1089

思路

之前做埃及分数的时候，由于这是紫书里介绍迭代加深的第一道题，在当时不了解迭代加深的原理再加上这题这么恶心的情况下，没咋明白。这回明白了。

思路详见代码注释

代码

#include "iostream"
#include "cstdio"
#include "cstring"
#include "cmath"
#include "set"
#define LL long long int
#define MAXK 5
#define MAXCS 100

using namespace std;
LL a, b,k,cs[MAXCS],ans[MAXCS];
set<int> ks; int cnt;

LL gcd(LL a, LL b) {
    return b == 0 ? a : gcd(b, a % b);
}
/*
找到第一个满足1/c<a/b的c

1/c<a/b
c<b/a
所以c为b/a向上取整或者b/a+1
*/
LL first_smaller_than(LL aa, LL bb) {
    return ceil(bb / (double)aa);
}
/*
因为题目中要求的是找到项数尽量小，最小的分数尽量大，第二小的分数尽量大...
所以先找到的答案可不一定是正确的，还得在此深度下继续查找

better判断当前的答案是否比已有答案更好
*/
bool better(int maxd) {
    for (int i = maxd ; i >= 0; i--) 
        if (cs[i] != ans[i])return ans[i]==-1||cs[i] < ans[i];
    return false;
}

/*
之前选择的是选择第d个1/c
最大选择maxd个1/c
当前离总目标a/b还差aa/bb
*/
bool dfs(int d,int maxd,LL first,LL aa, LL bb) {
    // 如果深度等于最大深度
    if (d == maxd) {
        // 如果最后一个满足1/x的形式并且不在ks中
        if (bb % aa || ks.count(bb / aa))return false;
        cs[d] = bb / aa;
        // 如比当前答案更好 更新
        if (better(maxd)) {
            memcpy(ans, cs, sizeof(cs));
            return true;
        }
        return false;
    }

    first = max(first,first_smaller_than(aa,bb));
    bool ok = false;
    // 往后依次遍历每一个c
    for (int c = first;; c++) {
        // 如果c在ks里，不要
        if (ks.count(c) != 0)continue;
        // 如果后面的有限个都用1/c还是凑不够aa/bb，剪枝
        if (bb*(maxd+1-d)<=aa*c) 
            break;
        cs[d] = c;  
        // 算新的aabb，并通分
        LL naa=aa*c-bb, nbb = bb*c;
        LL g = gcd(nbb, naa);
        if (dfs(d + 1, maxd,c+1, naa/g, nbb/g))ok = true;
    }
    return ok;
}

int main() {
   int T;
   scanf("%d", &T);
   for (int kase = 1; kase <= T; kase++) {
       scanf("%lld %lld %d", &a, &b, &k);
       ks.clear();
       for (int i = 0; i < k; i++) { int tmp; scanf("%d", &tmp); ks.insert(tmp); }
        for (int maxd = 1;; maxd++) {
            memset(ans, -1, sizeof(ans));
            cnt = 0;
            if (dfs(0, maxd,first_smaller_than(a,b), a, b)) {
                printf("Case %d: %lld/%lld=", kase, a, b);
                for (int j = 0; j <= maxd; j++) {
                    printf("1/%lld", ans[j]);
                    if (j < maxd)printf("+");
                }
                printf("\n");
                break;
            }
        }
   }
    return 0;
}