北京大学---最简真分数（欧几里得辗转相除求最大公约数）

本文主要是介绍北京大学---最简真分数（欧几里得辗转相除求最大公约数），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述
给出n个正整数，任取两个数分别作为分子和分母组成最简真分数，编程求共有几个这样的组合。
输入描述:
每组包含n（n<=600）和n个不同的整数，整数大于1且小于等于1000。
输出描述:
每行输出最简真分数组合的个数。
示例1
输入
7
3 5 7 9 11 13 15
输出
17

---

/** 依次以n个数中的每个数为分子，去找比它大的,且二者没有互质（即最大公约数为一）的数做分母,*/
#include <stdio.h>
int gcd(int a,int b){ //利用欧几里得算法求最大公约数if(b==0)return a;elsereturn gcd(b,a%b);}
int main(){int n;int a[1000];while(scanf("%d",&n)!=EOF){int sum=0;for(int i=0;i<n;i++){scanf("%d",&a[i]);}for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(i==j)continue;else if((a[i]>a[j])&&(gcd(a[i],a[j])==1)){sum++;}}}printf("%d\n",sum);}return 0;
}

这篇关于北京大学---最简真分数（欧几里得辗转相除求最大公约数）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---