网站备案掉了,海口网站制作,外贸建站哪家公司好,网站开发所使用的浏览器题目链接#xff1a;
最简真分数https://www.nowcoder.com/share/jump/437195121691719749588
描述
给出n个正整数#xff0c;任取两个数分别作为分子和分母组成最简真分数#xff0c;编程求共有几个这样的组合。
输入描述#xff1a;
每组包含n#xff08;n600
最简真分数https://www.nowcoder.com/share/jump/437195121691719749588
描述
给出n个正整数任取两个数分别作为分子和分母组成最简真分数编程求共有几个这样的组合。
输入描述
每组包含nn600和n个不同的整数整数大于1且小于等于1000。
输出描述
每行输出最简真分数组合的个数。
示例1
输入
7 3 5 7 9 11 13 15 3 2 4 5 0
输出
17 2
源代码
#includeiostream
#includevector
#includealgorithm
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时结束}vectorint 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;
}思路 读入整数 n代表接下来有 n 个整数。 使用一个 vector 存储这 n 个整数。 对 vector 中的整数进行排序方便后面的计算。 使用两层循环遍历所有的数对 (nums[i], nums[j])其中 i j。 对每对数分别计算最大公约数如果最大公约数为 1则说明这是一个最简真分数将计数器 res 增加 1。 输出最终的 res 值即最简真分数的数量。
提交结果
编辑切换为居中
添加图片注释不超过 140 字可选
