题目描述

给你一个整数 n，请你返回所有 0 到 1 之间（不包括 0 和 1）满足分母小于等于 n 的 最简 分数。分数可以以 任意 顺序返回。

样例

输入：n = 2
输出：["1/2"]
解释："1/2" 是唯一一个分母小于等于 2 的最简分数。

输入：n = 3
输出：["1/2","1/3","2/3"]

输入：n = 4
输出：["1/2","1/3","1/4","2/3","3/4"]
解释："2/4" 不是最简分数，因为它可以化简为 "1/2"。

输入：n = 1
输出：[]

限制

• 1 <= n <= 100

算法

(暴力枚举) $O(n^2 \log n)$

1. 从小到大枚举分母 b，在此基础上枚举分子 a，如果 a 与 b 互质，则将 a/b 加入答案。

时间复杂度

• 分别枚举 b 和 a，然后判定是否互质。
• 一次辗转相除的时间复杂度为 $O(\log n)$，故总时间复杂度为 $O(n^2 \log n)$。

空间复杂度

• 需要额外 $O(\log n)$ 的空间存储辗转相除的系统栈，以及 $O(n^2)$ 的空间存储答案。

C++ 代码

class Solution {
public:
    int gcd(int x, int y) {
        return y ? gcd(y, x % y) : x;
    }

    vector<string> simplifiedFractions(int n) {
        vector<string> ans;

        for (int b = 2; b <= n; b++)
            for (int a = 1; a < b; a++)
                if (gcd(a, b) == 1)
                    ans.push_back(to_string(a) + "/" + to_string(b));

        return ans;
    }
};