最简分数一定是真分数,1999999995最简分数

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

输入描述:

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

输出描述:

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

示例1

输入
7
3 5 7 9 11 13 15
3
2 4 5
0
输出
17
2

题解

用GCD求最大公倍数，如果分子小于分母且GCD返回值为1，那么计数+1

c++11 #include<cstdio>#include<iostream>#define N 600using namespace std;int GCD(int x,int y){ if (y==0) return x; else return GCD(y,x%y);}int main(){ int n,count; int buf[N]; while(cin>>n){ for(int i=0;i<n;i++){ cin>>buf[i]; } count=0; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(i==j) continue; else if(buf[i]>buf[j]&&GCD(buf[i],buf[j])==1) {count++;} } } cout<<count<<endl; } return 0;} 总结

GCD要背下来

int GCD(int x,int y){
if (y==0) return x;
else return GCD(y,x%y);
}