Phân số đơn giản hóa (Simplified Fractions) trong C++

Cho số nguyên n. Tìm tất cả phân số đơn giản hóa (tử và mẫu nguyên tố cùng nhau) nằm trong khoảng (0, 1) với mẫu số ≤ n. Kết quả có thể bất kỳ thứ tự.

Ví dụ

Đầu vào: n = 4
Đầu ra: ["1/2","1/3","1/4","2/3","3/4"] (loại "2/4" vì rút gọn thành "1/2").

Thuật toán duyệt mẫu số + GCD

1. Duyệt mẫu số i từ 2 đến n.
2. Duyệt tử số j từ 1 đến i-1.
3. Tính g = gcd(i, j). Phân số đơn giản: j/g / i/g.
4. Dùng set<string> để loại trùng lặp (do nhiều cặp rút gọn ra cùng phân số).
5. Chuyển set sang vector trả về.

Triển khai C++

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

class Solution {
public:
    vector<string> simplifiedFractions(int n) {
        vector<string> res;
        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j < i; ++j) {
                int g = gcd(i, j);
                res.push_back(to_string(j/g) + "/" + to_string(i/g));
            }
        }
        sort(res.begin(), res.end());
        res.erase(unique(res.begin(), res.end()), res.end());
        return res;
    }
};

Độ phức tạp

• Thời gian: O(N^2 log N) - lặp~i^2 cặp, gcd O(log N), sắp xếp O(K log K).
• Không gian: O(K) lưu kết quả, K ≈ 3N^2/π^2.

Kết quả kiểm thử

Đầu vào: 4
Đầu ra: [1/2, 1/3, 1/4, 2/3, 3/4]