题解 | 最简真分数

#include <iostream>
using namespace std;

const int N = 610;
int a[N];

int gcd(int x,int y){
    return y ? gcd(y,x%y):x;
}
int main() {
    //判断是否是最简真分数的思路就是
    //先判断是否是真分数
    //然后判断是否是最简
    int n;
    while(cin>>n){
        if(n==0)break;
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        int count = 0;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++){
                if(a[i]>=a[j])continue;
                else{
                    int x = gcd(a[i],a[j]);
                    if(x==1)count++;
                }
            }

        cout<<count<<endl;
    }
}
// 64 位输出请用 printf("%lld")