题解 | #最简真分数#

求互质用欧几里得算法，遍历可以暴力二重循环，也可以先排序，然后第二层循环从i+1开始，因为分母必须大于分子，两种方法都可以过，而且暴力还容易写点。

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

int n;
int a[605];

int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}

int main()
{
    while (cin >> n && n != 0)
    {
        for (int i = 0; i < n; ++i)
            cin >> a[i];
        sort(a, a + n);
        int cnt = 0;
        for (int i = 0; i < n; ++i)
            for (int j = i + 1; j < n; ++j)
                if (a[j] % a[i] != 0 && gcd(a[j], a[i]) == 1)
                    ++cnt;
        cout << cnt << endl;
    }
    return 0;
}