最简真分数

[编程题]最简真分数

热度指数：19257 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

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

输入描述:

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

输出描述:

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

示例1

输入

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

输出

17 
2

算法知识视频讲解

ygl45

#include<stdio.h>

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

int main()
{
	int a[601];
	int n,i,j;
	while(~scanf("%d",&n))
	{
        if(n==0) return 0;
        else{
            int sum=0;
		    for(i=0;i<n;i++)
				scanf("%d",&a[i]);

			for(i=0;i<n-1;i++)
				for(j=i+1;j<n;j++)
					if(gcd(a[i],a[j])==1) sum++;
			printf("%d\n",sum);
        }
		
	}
	return 0;
}

发表于 2022-03-23 17:56:54 回复(0)

Gargantua

#include<stdlib.h>
#include<stdbool.h>
#include<stdio.h>
bool Judge(int a,int b){//a分子，b分母
	for(int i=2;i<=a;i++){
		if(a%i==0 && b%i==0)
			return false;
	}
	return true;
}
//最简真分数
int main(){
	int n;
	while(scanf("%d",&n)!=EOF){
		if(n==0)break;
		else{
			int sum=0;
			int *num=(int *)malloc(sizeof(int)*n);
			for(int i=0;i<n;i++){
				int temp;
				scanf("%d",&temp);
				num[i]=temp;
			}
			for(int j=0;j<n;j++){ //分子
				for(int k=0;k<n;k++){ // 分母
					if(j!=k && num[j]<num[k] && Judge(num[k],num[j]))
						sum++;
				}
			}
			printf("%d",sum);
			printf("\n");
		}
	}
}

实际上，这里求gcd复杂度高了，可以优化。

发表于 2022-01-09 12:41:57 回复(0)