题目描述
给出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;
}
