HJ82 将真分数分解为埃及分数

描述

分子为1的分数称为埃及分数。现输入一个真分数(分子比分母小的分数，叫做真分数)，请将该分数分解为埃及分数。如：8/11 = 1/2+1/5+1/55+1/110。

注：真分数指分子小于分母的分数，分子和分母有可能gcd不为1！

如有多个解，请输出任意一个。

示例：

输入：

8/11
2/4

输出：

1/2+1/5+1/55+1/110
1/3+1/6

说明：

第二个样例直接输出1/2也是可以的

思路：

方法一：投机取巧

直接输出当前字母的各种 1/字母即可。

#include <bits/stdc++.h>
using namespace std;

int main(){
    string str;
    while(cin >> str){
        int index = str.find('/');
        string a = str.substr(0, index);
        string b = str.substr(index + 1);
        int n = stoi(a);
        string res;
        while(n--){
            res += "1/" + b + "+";
        }
        res = res.substr(0, res.size() - 1);
        cout << res << endl;
    }
    return 0;
}

方法二：数学推导

我们假设 a/b

\[ \frac{b}{a} = x{\ldots}y \]

\[ b = ax + y \]

\[ \frac{a}{b} = \frac{a}{ax + y} = \frac{a(x+1)}{ax+y(x+1)} \]

\[ \implies = \frac{a(x+1) + y - y}{(ax+y)(x+1)} = \frac {1}{x+1} + \frac {a-y}{y} * \frac {1}{x+1} \]

#include <bits/stdc++.h>
using namespace std;


int main(){
    string str;
    while(cin >> str){
        int index = str.find('/');
        string tmp1 = str.substr(0, index);
        string tmp2 = str.substr(index + 1);
        int a = stoi(tmp1);
        int b = stoi(tmp2);
        
        while(a != 1){
            if(b % a == 0){
                b = b / a;
                break;
            }
            //按照公式划分
            int x = b / a;
            int y = b % a;
            cout << 1 << "/" << x + 1 << "+";
            a -= y;
            b *= (x + 1);
        }
        cout << 1 << "/" << b << endl;
    }
    return 0;
}