【五月份 -- 基础语法组】-- T3 -- 排序

zhangyuqiTAT · 2025-05-13 16:41:02 · 个人记录

https://cspjs.online/contest/688/problem/3

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int gcd(int a, int b);

struct Fraction {
    int numerator;    // 分子
    int denominator;  // 分母
    double value;     // 分数值（用于排序）

    Fraction(int n, int d) : numerator(n), denominator(d) {
        int g = gcd(n, d);
        numerator /= g;
        denominator /= g;
        value = static_cast<double>(numerator) / denominator;
    }
};

int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

// 比较函数，用于std::sort
bool compareFractions(const Fraction& f1, const Fraction& f2) { return f1.value < f2.value; }

int main() {
    freopen("sort.in", "r", stdin);
    freopen("sort.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    vector<Fraction> fractions;

    // 生成并筛选分数
    for (int i = 2; i <= n; ++i) {     // 分母从2开始
        for (int j = 1; j < i; ++j) {  // 分子从1到分母-1
            if (gcd(i, j) == 1) {
                fractions.emplace_back(j, i);
            }
        }
    }

    // 排序
    sort(fractions.begin(), fractions.end(), compareFractions);

    // 输出
    for (const auto& f : fractions) {
        cout << f.numerator << " " << f.denominator << endl;
    }

    return 0;
}