描述
给出n个正整数,任取两个数分别作为分子和分母组成最简真分数,编程求共有几个这样的组合。
输入描述:
每组包含n(n<=600)和n个不同的整数,整数大于1且小于等于1000。
输出描述:
每行输出最简真分数组合的个数。
示例1
输入:
7
3 5 7 9 11 13 15
3
2 4 5
0
输出:
17
2
#include<stdio.h>
using namespace std;
/* 任何两个数,如果它们的最大公约数=1, 则它们可以组成一个最简真分数。最大公约数可以用辗转相除法 */
int gcd(int a, int b) {
if (b==0) {
return a;
} else {
return gcd(b, a%b);
}
}
int main() {
// 最简真分数 分子和分母不能再化简的分数
int n;
while (scanf("%d", &n) != -1) {
if (n==0) {
continue;
}
int arr[n];
int count=0;
for (int i=0; i<n; i++) {
scanf("%d",&arr[i]);
}
// i,j的初始值和结束值要防止重复判断 比如2/5 和5/2组成的算是一个
for (int i=0; i<n-1; i++) {
for (int j=i+1; j<n; j++) {
if (gcd(arr[i],arr[j])==1) {
count++;
}
}
}
printf("%d\n",count);
}
return 0;
}
文章评论