[保研/考研机试] KY35 最简真分数 北京大学复试上机题 C++实现

题目链接：

最简真分数https://www.nowcoder.com/share/jump/437195121691719749588

描述

给出n个正整数，任取两个数分别作为分子和分母组成最简真分数，编程求共有几个这样的组合。

输入描述：

每组包含n（n<=600）和n个不同的整数，整数大于1且小于等于1000。

输出描述：

每行输出最简真分数组合的个数。

示例1

输入：

7 3 5 7 9 11 13 15 3 2 4 5 0

输出：

17 2

源代码：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;// 辗转相除法求最大公约数
int GCD(int a, int b) {if (b == 0) {return a;}else {return GCD(b, a % b);}
}int main() {int n;while (cin >> n) {if (n == 0) {break; // 输入为0时结束}vector<int> nums; // 存储输入的整数int res = 0; // 存储最简真分数的数量for (int i = 0; i < n; i++) {int temp;cin >> temp;nums.push_back(temp);}sort(nums.begin(), nums.end()); // 对输入的整数进行排序for (int i = 0; i < n; i++) {for (int j = i + 1; j < nums.size(); j++) {if (GCD(nums[i], nums[j]) == 1) {res++; // 若最大公约数为1，则说明是最简真分数，计数加1}}}cout << res << endl; // 输出最简真分数的数量}return 0;
}

思路：

1. 读入整数 n，代表接下来有 n 个整数。

2. 使用一个 vector 存储这 n 个整数。

3. 对 vector 中的整数进行排序，方便后面的计算。

4. 使用两层循环遍历所有的数对 (nums[i], nums[j])，其中 i < j。

5. 对每对数分别计算最大公约数，如果最大公约数为 1，则说明这是一个最简真分数，将计数器 res 增加 1。

6. 输出最终的 res 值，即最简真分数的数量。

提交结果：

​

编辑切换为居中

添加图片注释，不超过 140 字（可选）