1447. Simplified Fractions

题目信息

题号:

1447

难度:

Medium

主题:

数论、最大公约数、枚举

原题:

LeetCode 1447

重点:

枚举 0 < 分子 < 分母 <= n 且分子分母互质的最简真分数;返回顺序不限

题目重述

给定整数 n。请返回所有位于 0 与 1 之间的最简分数,要求分母不超过 n。

每个结果以字符串 "分子/分母" 表示;分子和分母的最大公约数必须为 1。返回顺序不限。

2 <= n <= 100。

自建示例

不同分母下只保留最简形式:

输入:n = 3
输出:["1/2","1/3","2/3"]
解释:分母不超过 3 的最简真分数只有这三个。

最小允许分母只产生一个分数:

输入:n = 2
输出:["1/2"]
解释:唯一满足条件的分子为 1。