OpenJudge NOI 2.1 3526:最简真分数

【题目链接】

OpenJudge NOI 2.1 3526:最简真分数

【题目考点】

1. 枚举

2. 最大公约数

3. 分数概念

【解题思路】

最简真分数的概念为：分子小于分母,且分子和分母互质的分数
两个数互质，等价于两个数的最大公约数为1。
求最大公约数的方法见：
信息学奥赛一本通 1207：求最大公约数问题 | OpenJudge 2.2 7592:求最大公约数问题

枚举三要素：

• 枚举对象：两个数
• 枚举范围：序列范围内的数字
• 判断条件：两个数互质。
  由于序列中的数字两两不同，只要这两个数互质，那么就可以构成一个最简真分数。

序列中数字数量最大为600。对于数字个数为n的序列，所有可能的数对个数为$1+2+...+(n-1)=n(n-1)/2=179700$，可以枚举。

【题解代码】

解法1：枚举 递归求最大公约数

#include
using namespace std;
int gcd(int a, int b)
{
	if(b == 0)
		return a;
	return gcd(b, a%b);
}
int main()
{
	int n, a[605], ct = 0;
	cin >> n;
	for(int i = 1; i <= n; ++i)
		cin >> a[i];
	for(int i = 1; i <= n-1; ++i)
		for(int j = i+1; j <= n; ++j)
		{
			if(gcd(a[i], a[j]) == 1)
				ct++;
		}
	cout << ct;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

解法2：枚举 迭代求最大公约数

#include
using namespace std;
int gcd(int a, int b)
{
	int t;
	while(b > 0)
	{
		t = a%b;
		a = b;
		b = t;
	}
	return a;
}
int main()
{
	int n, a[605], ct = 0;
	cin >> n;
	for(int i = 1; i <= n; ++i)
		cin >> a[i];
	for(int i = 1; i <= n-1; ++i)
		for(int j = i+1; j <= n; ++j)
		{
			if(gcd(a[i], a[j]) == 1)
				ct++;
		}
	cout << ct;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28