最简真分数

http://t.cn/AiCua2g8

描述

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

输入描述：

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

输出描述：

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

示例1

输入：

7
3 5 7 9 11 13 15
3 
2 4 5
0

输出：

17 
2

#define _CRT_SECURE_NO_WARNINGS 1
#include <bits/stdc++.h>
using namespace std;

const int N = 610;
int arr[N];

int GCD(int a, int b) {
	if (b == 0)
		return a;
	else
		return GCD(b, a % b);
}

int main() {
	int n;
	while (cin >> n)
	{
		if (n == 0)
			break;
		for (int i = 0; i < n; ++i)
			cin >> arr[i];
		int answer = 0;
		for (int i = 0; i < n; ++i) {
			for (int j = i + 1; j < n; ++j) {
				if (GCD(arr[i], arr[j]) == 1)
					answer++;
			}
		}
		cout << answer << endl;
	}
	return 0;
}