题目
给定n个数，任取其中两个，计算组成的真分数的个数。
思路
计算两个数的最大公约数，只需保证这两个数的最大公约数为1。
代码
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int gcd(int a, int b)
{
return b == 0 ? a : gcd(b, a % b);
}
int main()
{
int n;
while(cin >> n) {
int x, cnt = 0;
vector<int> v;
for(int i = 0; i < n; i++) {
cin >> x;
v.push_back(x);
}
sort(v.begin(), v.end());
for(int i = 0; i < v.size()-1; i++) {
for(int j = i+1; j < v.size(); j++) {
if(gcd(v[i], v[j]) == 1) cnt++;
}
}
cout << cnt << endl;
}
return 0;
}
最大公约数
int gcd(int a, int b)
{
return b == 0 ? a : gcd(b, a % b);
}
