【描述】

真分数，指的是分子比分母小的分数，真分数的分数值小于1。

给出n个正整数，任取两个数分别作为分子和分母组成真分数。

求能组成多少不同值的真分数。

【输入】

第一行是一个正整数n。

第二行是n个不同的正整数ai，相邻两个整数之间用单个空格隔开。

【输出】

一个整数，即最简真分数组合的个数。

【样例输入输出】

    样例说明：共组成6个真分数：1/2，1/3，1/4，2/3，2/4，3/4。

但是这6个真分数有5个不同的值：1/2，1/3，1/4，2/3，3/4。因为1/2和2/4的值相同.

【数据范围】

100%的数据：1<=ai<=1000，n<=600。

【来源】

2019年青岛市程序设计竞赛试题（初中组）1T

【题目分析】

• 题目比较简单，模拟法求解即可 

• 题目保证输入的数据不同，也就是不存在1/1这样的数

• 可以先把数据排序，然后进行组合。

• 对于组合后的数据如果存在重复的进行筛选即可

• 筛选的过程可以用最大公约数和桶排的方法进行筛选
  

【参考答案】

#include<cstdio>
#include<algorithm> 
using namespace std;
int fz[601],fm[601]; //分子和分母
int n;//
int flagfz[601],flagfm[601]; //标记数组
int devisor; //最大公约数 
//求最大公约数 
int gcd(int a,int b)
{
    if(b==0)
        return a;
    return gcd(b,a%b);
} 
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&fz[i]);
		fm[i]=fz[i];
	}
	sort(fz,fz+n);
	sort(fm,fm+n); //分子分母排序 
	//处理数据
	int k=0,q=0; 
	for(int i=0;i<n;i++)
	{
		for(int j=i+1;j<n;j++)
		{
			devisor=gcd(fz[i],fm[j]);
			//printf("%d /%d\n",fz[i],fm[j]);
			flagfz[k]=fz[i]/devisor;
			flagfm[k]=fm[j]/devisor;//约分 
			printf("%d/%d\n",flagfz[k],flagfm[k]);
			//约分后的数据看看以前有没有出现过
			for(int p=0;p<k;p++){
				if(flagfz[p]==flagfz[k] && flagfm[p]==flagfm[k])	
				q++; //找到重复的数据 
			}
			k++; //计数器加1 
		} 
	} 
	printf("%d",k-q); 
	return 0; 
}