题解 | #将真分数分解为埃及分数#

思路：

寻找一个合适的比例，原a/b, 找到一个c，新a*c/b*c。假设c的范围[2, b]

即转化为：在b*c的众多因子中，寻找部分因子和 == a*c

(1) 遍历c，找到b*c的所有因子并保存。因子定义域[1, b*c]，当满足b * c % k == 0时，保存；

(2) 对所有因子进行部分求和，是否满足其和 == a*c，即是否存在解路径

    dfs函数进行操作。保存中间路径。

#include <iostream>
#include <vector>
#include <sstream>
#include <cmath>
using namespace std;

/*
<花费时间：1.08h>
*/

vector<int> ans_path;
bool find_path(vector<int>& inte, int res, int i, int target, vector<int> path){
    // cout << "find_path_i: " << i << endl;
    bool ans = false;
    if(i == inte.size()){
        if(res == target) {
            ans_path = path;
            return true;
        }
        return false;
    }
    vector<int> cur_path = path;
    cur_path.push_back(i);
    ans |= find_path(inte, res + inte[i], i + 1, target, cur_path);

    // 不取
    ans |= find_path(inte, res, i+1, target, path);
    return ans;


}

int main() {
    string s;
    while(cin >> s){
        istringstream ss(s);
        vector<int> inte;
        string tmp;
        while(getline(ss, tmp, '/')){
            // cout << tmp << endl;
            inte.push_back(stoi(tmp));
        }

        // 遍历寻找，找到一个合适的放大因子
        for(int c = 2; c <= inte[1]; c ++){
            int new_mom = inte[1] * c;

            vector<int> cur_yinzi;
            for(int i = 1; i < new_mom; i++){
                if(new_mom % i == 0) cur_yinzi.push_back(i);
            }

            // 观察因子和是否，找到inte[0]*c的解。
            int cur_sum = 0;
            for(auto in : cur_yinzi) cur_sum += in;
            if(cur_sum < inte[0] * c) continue;

            vector<int> tmp_path;
            // cout << cur_yinzi.size() << endl;
            find_path(cur_yinzi, 0, 0, inte[0] * c, tmp_path);
            // cout << ans_path.size() << endl;
            if(ans_path.size() != 0){
                for(int j = 0; j < ans_path.size(); j++){
                    // cout << cur_yinzi[ans_path[j]] << endl;
                    cout << "1/" << to_string(inte[1] * c / cur_yinzi[ans_path[j]]);
                    if(j != ans_path.size() - 1) cout << "+";
                }
                cout << endl;
                break;
            }

        }

    }



}
// 64 位输出请用 printf("%lld")