P1572题解

lkrqwq · 2024-02-10 15:25:08 · 题解

今天看见一大堆题解被撤了，顺便来写一篇题解增加咕值。

这其实是小学数学，已知：

根据这个公式，我们可以用 C++ 模拟这个过程：

int now = lcm(fm, b); //fm,b的最小公倍数
a = a * (now / b); //通分
b = now; 
fz = fz * (now / fm);
fm = now;
fz += a; //累加

通分后，我们还要把分子和分母同除以 \gcd(fz,fm)（也就是约分），避免超出长整型的数据范围。

算好后，再约分一下，看看分母是否为 1，如果是，那么直接输出分子；否则，如果分子为 0，输出 0 即可；

如果上面条件都不成立，就判断分子分母的正负性。如果分子分母有一个是负，那么把符号移到最前面；否则，直接输出分子和分母。

#include <iostream>
#include <string>
using namespace std;
#define int long long
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
int sgn(int x) {
    if (x > 0) return 1;
    if (x < 0) return -1;
}
signed main() {
    int fz = 0, fm = 0; 
    int a, b; char ch;
    cin >> a >> ch >> b, fz = a, fm = b;
    while (cin >> a >> ch >> b) {
        int nowb = lcm(fm, b);
        a = a * (nowb / b);
        b = nowb;
        fz = fz * (nowb / fm);
        fm = nowb;
        fz += a;
        int t = gcd(fz, fm);
        fz /= t, fm /= t;
    }
    int t = gcd(fz, fm);
    fz /= t, fm /= t;
    if (fz % fm == 0) { //或if (fm == 1)
        cout << fz / fm;
    }
    else {
        if (fz == 0) {
            cout << 0;
        }
        else {
            if (sgn(fz) == -sgn(fm)) {
                cout << "-" << abs(fz) << "/" << abs(fm);
            }
            else {
                cout << fz << "/" << fm;
            }
        }
    }
}

感谢 Bingxiu 提供的 hack 数据：

输入 #1：

1/625+624/625+1/343+342/343+1/121+120/121+1/169+168/169+1/289+288/289+1/529+528/529+1/512+1/729

输出 #1：

2240729/373248

输入 #2：

2/4

输出 #2：

1/2

本程序已经过测试，保证能通过这些数据。