埃及分數拆分的過程，埃及分數問題+迭代加深搜索

• 理論上可以用回溯法求解，但是解答樹非常恐怖，其一深度沒有明顯上限，1/i的值似乎可以在枚舉不斷更大的i時越來越小；其二加數的選擇在理論上無限制。
• 解決方案采用迭代加深搜索：從小到大枚舉深度上限maxd，每次只執行深度不超過maxd的結點。這樣，if(bb*(maxd+1-d)<=i*aa) break;在i++到一定值后一定會退出循環，不會在已經得到解的情況下繼續往下遞歸
• 埃及分數這道題題意說加數少的比加數多的好，所以在主程序當前maxd下，得到了解ok=1,則不管接下來的maxd,程序結束

?

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cassert>
using namespace std;
int a, b, maxd;
typedef long long LL;
LL gcd(LL a, LL b)  //輾轉相除法，求最大公因子
{return b == 0 ? a : gcd(b, a%b);
}
// 返回滿足1/c <= a/b的最小c
inline int get_first(LL a, LL b)
{return b/a+1;
}
const int maxn = 100 + 5;
LL v[maxn], ans[maxn];
// 如果當前解v比目前最優解ans更優，更新ans這一判斷的依據
bool better(int d)  //前d個，這時d只能是maxd，
{for(int i = d; i >= 0; i--) if(v[i] != ans[i]){return ans[i] == -1 || v[i] < ans[i];//沒被訪問過，或者是當前序列更優}return false;
}
// 當前深度為d，分母(注意是分母)不能小于from，分數之和恰好為aa/bb
bool dfs(int d, int from, LL aa, LL bb)
{if(d == maxd){if(bb % aa) return false; // aa/bb必須是埃及分數（任何數mod1都等于0，可以起到一部分剪枝的作用）v[d] = bb/aa;//不用再進一步展開分數if(better(d)) memcpy(ans, v, sizeof(LL)*(d+1));return true;}bool ok = false;//最后一層沒找到解，可向上返回from = max(from, get_first(aa, bb)); // 枚舉的起點( 越大，取倒之后就越小）for(int i = from; ; i++)  //進行枚舉{// 剪枝：如果剩下的maxd+1-d個分數全部都是1/i，加起來仍然不超過aa/bb，則無解if(bb * (maxd+1-d) <= i * aa) break;//從第0層開始算的，總共有maxn+1個v[d] = i;// 計算aa/bb - 1/i，設結果為a2/b2LL b2 = bb*i;LL a2 = aa*i - bb;LL g = gcd(a2, b2); // 以便約分if(dfs(d+1, get_first(a2/g, b2/g), a2/g, b2/g)) ok = true;}return ok;//注意這些返回條件
}int main()
{int kase = 0;while(cin >> a >> b){int ok = 0;for(maxd = 1; maxd <= 100; maxd++)  //從小到大，枚舉深度上限{memset(ans, -1, sizeof(ans));if(dfs(0, get_first(a, b ), a, b)){ok = 1;//找到解了~~break;}}cout << "Case " << ++kase << ": ";if(ok){cout << a << "/" << b << "=";for(int i = 0; i < maxd; i++) cout << "1/" << ans[i] << "+";cout << "1/" << ans[maxd] << "\n";}else cout << "No solution.\n";}return 0;
}