1447. Simplified Fractions¶
题目信息¶
- 题号:
1447
- 难度:
Medium
- 主题:
数论、最大公约数、枚举
- 原题:
- 重点:
枚举
0 < 分子 < 分母 <= n且分子分母互质的最简真分数;返回顺序不限
题目重述¶
给定整数 n。请返回所有位于 0 与 1 之间的最简分数,要求分母不超过 n。
每个结果以字符串 "分子/分母" 表示;分子和分母的最大公约数必须为 1。返回顺序不限。
2 <= n <= 100。
自建示例¶
不同分母下只保留最简形式:
输入:n = 3
输出:["1/2","1/3","2/3"]
解释:分母不超过 3 的最简真分数只有这三个。
最小允许分母只产生一个分数:
输入:n = 2
输出:["1/2"]
解释:唯一满足条件的分子为 1。