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