题解 | #最简真分数#

#include <iostream>
using namespace std;
//如果两个数的最大公因子是1,则两个数可以组成最简真分数
const int N=610;
int a[N];
int n;
//判断两个数有没有公因子
int gcd(int a,int b){
    while(a%b){
        int c=a%b;
        a=b;
        b=c;
    }
    return b;
}
int cnt_fs(int a[]){
    int res=0;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(gcd(a[i], a[j])==1) res++;
        }
    }
    return res;
}
int main() {
    while(cin>>n&&n>0){
        for(int i=0;i<n;i++) cin>>a[i];
        cout<<cnt_fs(a)<<endl;
    }
    return 0;
}
// 64 位输出请用 printf("%lld")