题解 | #最简真分数#

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

int a[2000];

//将问题转换为求最大公约数
int gcd(int a, int b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}

int main() {
    int n, i, j, sum;
    while (scanf("%d", &n) != EOF && n != 0) {
        for (i = 0; i < n; i++) scanf("%d", &a[i]);
        for (i = 0, sum = 0; i < n; i++) {
            for (j = i + 1; j < n; j++) { //如果最大公约数为1，说明不能再化简了
                if (gcd(a[i], a[j]) == 1) sum++;
            }
        }
        printf("%d\n", sum);
    }
    return 0;
}