题目描述：

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

输入：

输入有多组，每组包含n（n<=600）和n个不同的整数，整数大于1且小于等于1000。
当n=0时，程序结束，不需要处理这组数据。

输出：

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

样例输入：

73 5 7 9 11 13 153 2 4 50

样例输出：

17 2

此题两两选择，若最大公约数为1，则是最简真分数

代码如下

 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 using namespace std; 6  7 int num[620]; 8  9 int calGCD(int a, int b) {10     int sum = a + b;11     a = max(a, b);12     b = sum - a;13     if (b == 0) {14         return a;15     }16     return calGCD(b, a%b);17 }18 19 int main() {20     int    n;21     while (scanf("%d", &n) != EOF && n != 0) {22         for (int i = 0; i < n; i++) {23             scanf("%d", &num[i]);24         }25         int ans = 0;26         for (int i = 0; i < n; i++) {27             for (int j = i + 1; j < n; j++) {28                 if (calGCD(num[i], num[j]) == 1) {29                     ans++;30                 }31             }32         }33         printf("%d\n", ans);34     }35     return 0;36 }

 

注意求最大公约数的代码，可以写的十分简洁，

辗转相除法

1 int gcd(int a, int b) {2     if (b == 0) return a;3     return gcd(b, a%b);4 }

 

九度oj 题目1465：最简真分数