55
九度1465：最简真分数
题目1465：最简真分数
时间限制：1 秒
内存限制：128 兆
特殊判题：否
提交：1330
解决：551
题目描述：
给出n个正整数，任取两个数分别作为分子和分母组成最简真分数，编程求共有几个这样的组合。
输入：
输入有多组，每组包含n（n<=600）和n个不同的整数，整数大于1且小于等于1000。
当n=0时，程序结束，不需要处理这组数据。
输出：
每行输出最简真分数组合的个数。
样例输入：
7
3 5 7 9 11 13 15
3
2 4 5
0
样例输出：
17
2
来源：
2012年北京大学计算机研究生机试真题
AC代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[1000];
int gdc(int n,int m)//最小公倍数
{
if(n%m==0)
return m;
else
return gdc(m,n%m);
}
int main()
{
int i,j,n,sum;
while(scanf("%d",&n),n!=0)
{
memset(a,0,sizeof(a));
for(i=0;i<n;i++)
scanf("%d",&a[i]);
sort(a,a+n);
sum=0;
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(a[j]>a[i]&&gdc(a[j],a[i])==1)//最小公倍数为一则分数为最简
{
sum++;
}
}
}
printf("%d\n",sum);
}
return 0;
}
最后更新：2017-04-03 12:56:01