34. 最简真分数

题目描述

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

输入描述:

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

输出描述:

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

示例1

输入

7
3 5 7 9 11 13 15

输出

17

解法

#include <stdio.h>
#include <malloc.h>

int gcd(int a, int b) {    //欧几里得算法求最大公约数
    if (a % b == 0)
        return b;
    else 
        return gcd(b, a % b);
}

int main() {
    for (int n, count = 0; ~scanf("%d", &n);) {
        int *num = (int *) malloc (sizeof(int) * n);
        for (int i = 0; i < n; i++)
            scanf("%d", &num[i]);
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                if (gcd(num[i], num[j]) == 1)    //题目说了数据是不相同的，所以最大公约数为 1 的两个数一定符合题意
                    count++;
        printf("%d\n", count);
        free(num);
    }
    return 0;
}