欢迎访问==> 【考研OR保研】机试题
题目描述
给出 $n$ 个正整数,任取两个数分别作为分子和分母组成最简真分数,编程求共有几个这样的组合。
输入格式
输入包含多组测试数据。
每组数据第一行包含整数 $n$。
第二行包含 $n$ 个整数,范围 $\[1,1000\]$ 且互不相同。
当 $n=0$ 时表示输入结束。
输出格式
每组数据输出一行结果,表示最简真分数组合的个数。
数据范围
$2 \\le n \\le 600$,
每个输入最多包含 $100$ 组数据。
输入样例:
7
3 5 7 9 11 13 15
3
2 4 5
0
输出样例:
17
2
C++ 代码
/*
预备基础知识:__gcd内置函数可以求两个数的最大公因数
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 610;
int n, a[N];
int main()
{
while(cin >> n && n != 0)
{
int cnt =0 ;
for(int i = 0; i < n; i ++) cin >> a[i];
sort(a, a + n); //排序,保证枚举的时候a[i] < a[j]
for(int i = 0; i < n; i ++)
{
for(int j = i + 1; j < n; j ++)
{
//当a[i]和b[j]的最大公因数为1时,满足题意
if(__gcd(a[i], a[j]) == 1) cnt ++;
}
}
cout << cnt << endl;
}
return 0;
}