92 最简真分数 北大复试

给出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 600
using 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);
}