1062. 最简分数.md

【PAT B-1062】最简分数

题意概述

一个分数一般写成两个整数相除的形式：N/M，其中 M 不为 0。最简分数是指分子和分母没有公约数的分数表示形式。现给定两个不相等的正分数$N_1/M_1$和$N_2/M_2$，要求你按从小到大的顺序列出它们之间分母为 K 的最简分数。

输入输出格式

输入在一行中按N/M的格式给出两个正分数，随后是一个正整数分母 K，其间以空格分隔。题目保证给出的所有整数都不超过 1000。

在一行中按N/M的格式列出两个给定分数之间分母为 K 的所有最简分数，按从小到大的顺序，其间以 1 个空格分隔。行首尾不得有多余空格。题目保证至少有 1 个输出。

算法设计

就样例来说，我们可以把 7/18 和 13/20 都通分成以 12 为分母的分数，即约为 4.67/12 和 7.8/12。那么在这两个分数之间的最简分数自然为 5/12 和 7/12。所以算法逻辑也就非常清晰了，将两个输入的分数均化成以给定整数为分母的分数，从小的分数的分子向大的分数的分子进行遍历，查找所有与给定整数互质（即最大公约数为 1）的分子，即为所求。

注意点

1. 输入的两个分数的谁大谁小不确定，需进行简单的判断。
2. 如果给出两个分数有以给定的 K 为分母的最简分数，则该分数不予输出。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
gg gcd(gg a, gg b) { return b == 0 ? a : gcd(b, a % b); }
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    gg ki, a1, b1, a2, b2;
    char c;
    cin >> a1 >> c >> b1 >> a2 >> c >> b2 >> ki;
    double n1 = (a1 * 1.0 * ki / b1), n2 = (a2 * 1.0 * ki / b2);
    if (n1 > n2)
        swap(n1, n2);
    bool space = false;
    for (gg i = floor(n1 + 1); i <= ceil(n2 - 1); ++i) {
        if (gcd(i, ki) == 1) {
            cout << (space ? " " : "") << i << '/' << ki;
            space = true;
        }
    }
    return 0;
}