题解 | #最简真分数#

#include <stdio.h>

// 辗转相除法求最大公约数
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main() {
    int n, a[605];
    while (scanf("%d", &n) != EOF) {
        if (n == 0) break;
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
        }
        int cnt = 0;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                // 判断是否互质且分子小于分母
                if (gcd(a[i], a[j]) == 1) {
                    cnt++;
                }
            }
        }
        printf("%d\n", cnt);
    }
    return 0;
}