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

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
vector<vector <int>> zuhe(vector<int> in, int target) {//target 是希望选择M个作组合,in是选择的范围，长度为N
    vector<vector <int>> output;
    for (int i = 0; i < pow(2, in.size()); i++) {
        int temp = 0, count = 0;
        vector<int> weishu;
        for (int j = 0; j < in.size(); j++) {
            if ((i & (1 << j)) != 0) {
                weishu.push_back(j); count++;
            }//找出二进制为1的位数以及它们的位置
        }
        if (count == target) {//位数等于M
            vector<int> one_case;
            for (int j = 0; j < count; j++) {
                temp = in.size() - 1 - weishu[j];
                one_case.push_back(in[temp]);
            }
            output.push_back(one_case);
        }
    }
    return output;
}
int main()
{
    string a;
   while(cin>>a){
        string b, c;
        for (int i = 0; i < a.length(); i++)
        {
            if (a[i] == '/')
            {
                b = a.substr(0, i);
                c = a.substr(i + 1, a.length() - i);
                break;
            }
        }
            int e = 0, f = 0;
            for (int i = 0; i < b.length(); i++)
            {
                e = e * 10 + b[i]-'0';
            }
            for (int i = 0; i < c.length(); i++)
            {
                f = f * 10 + c[i]-'0';
            }
        
            int g, h;
            for (int i = 1;i<f; i++)
            {
                g = e * i;
                h = f * i;
                vector<int>o;
                for (int j = 1; j <= h; j++)
                {
                    if (h % j==0)
                    {
                        o.push_back(j);
                        
                    }
                }
                for (int m = 1; m < o.size(); m++)
                {
                    vector<vector<int>>p = zuhe(o, m);
                    for (int n = 0; n < p.size(); n++)
                    {
                        int t = 0;
                        for (int k = 0; k < p[n].size(); k++)
                        {
                            t = t + p[n][k];
                        }
                        if (t == e * i)
                        {
                            for (int k = 0; k < p[n].size() - 1; k++)
                            {
                                cout << '1' << '/' << f * i / p[n][k] << '+';
                            }
                            cout << '1' << '/' << f * i / p[n].back();
                            goto w;
                        }
                    }
                }
            }
        
    w:
      continue;
   }
    return(0);
}