题解 | #最简真分数#

//土尔逊Torson 编写于2023/5/08
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>

using namespace std;

int GCD06801(int a, int b) { // a,b 的最大公约数 可以转换成 b, a mod b 的最大公约数
	if (b == 0) {            // a mod b: 表示 a 除以 b 后的余数 r
		return a;
	}
	else {
		return GCD06801(b, a%b);
	}
}

int main() {      //分子、分母只有公因数1的分数叫做最简分数
	int n;        //或者说分子和分母是互质数的分数,叫做最简分数
	int arr[601];
	while (scanf("%d", &n) != EOF) {
		for (unsigned int i = 0; i < n; ++i) {
			scanf("%d", &arr[i]);
		}

		int count = 0;
		for (unsigned int i = 0; i < n; ++i) {   // 解题为，分子、分母最大公因数为 1 的数为最简真分数
			for (unsigned int j = i + 1; j < n; ++j) { // 最大公因数 就是最大公约数
				if (GCD06801(arr[i], arr[j]) == 1) {
					count++;
				}
			}
		}

		if (count != 0) {
			printf("%d\n", count);
		}

	}
	system("pause");
	return EXIT_SUCCESS;
}
// 64 位输出请用 printf("%lld")