題目描述
給出n個正整數(shù)震束，任取兩個數(shù)分別作為分子和分母組成最簡真分數(shù)潜慎，編程求共有幾個這樣的組合缆巧。
輸入描述:
每組包含n（n<=600）和n個不同的整數(shù)，整數(shù)大于1且小于等于1000余境。
輸出描述:
每行輸出最簡真分數(shù)組合的個數(shù)。
示例1
輸入
7
3 5 7 9 11 13 15
輸出
17
解法
#include <stdio.h>
#include <malloc.h>
int gcd(int a, int b) { //歐幾里得算法求最大公約數(shù)
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) //題目說了數(shù)據(jù)是不相同的灌诅，所以最大公約數(shù)為 1 的兩個數(shù)一定符合題意
count++;
printf("%d\n", count);
free(num);
}
return 0;
}
