题解 | 最简真分数

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

//给出n个正整数，任取两个数分别作为分子和分母组成最简真分数，编程求共有几个这样的组合。

//每组包含n（n<=600）和n个不同的整数，整数大于1且小于等于1000。

//每行输出最简真分数组合的个数。

//思路： 先输入n个数组成的数组。
//       采用穷举法，arr[0] 和arr[1--n-1] 进行比较
//      比较方法：判断是否有除了1以外的公因子，若有，则sum++,否则继续比较


int compare(int a, int
            b) { //比较方法：判断是否有除了1以外的公因子，若有，则sum++,否则继续比较
    int maxNum;
    for (int i = 1; i <= min(a, b); i++) {
        if ((a % i == 0) && (b % i == 0)) {
            maxNum = i;
        }
    }
    return maxNum;
}

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        if (n == 0) {
            break;
        }
        vector<int> arr;
        for (int i = 0; i < n; i++) { //先输入n个数组成的数组。
            int m;
            scanf("%d", &m);
            arr.push_back(m);
        }
        //  采用穷举法，arr[0] 和arr[1--n-1] 进行比较 以此类推
        int sum = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (compare(arr[i], arr[j]) == 1) sum++;;
            }
        }
        printf("%d\n", sum);
    }
    return 0;
}