题解 | #最简真分数#

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

//习题6.5 最简真分数
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;
        }
        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++;
                }
            }
        }
        cout << res << endl;
    }

    return 0;
}
// 64 位输出请用 printf("%lld")