题解 | #最简真分数#

#include <algorithm>
#include <bits/stdc++.h>
#include <vector>
using namespace std;
//a<b
void zuixiaogongbeishu(int a,int b,int& zxgbs)
{
    if(a==b-a)
    {
        zxgbs=a;
        return;
    }
    if(a>b-a)
    zuixiaogongbeishu(b-a,a,zxgbs);
    else 
    zuixiaogongbeishu(a,b-a,zxgbs);
}
int main() {
    int n;
    while(cin>>n)
    {
        int data;
        int res=0;
        vector<int> num;
        while(n--)
        {
            cin>>data;
            num.push_back(data);
        }
        sort(num.begin(), num.end());
        for(int i=0;i<num.size();i++)
        {
            for(int j=i+1;j<num.size();j++)
            {
                if(num[j]%num[i]==0) continue;//小优化
                int zxgbs;
                zuixiaogongbeishu(num[i],num[j],zxgbs);
                //最小公倍数是1的话就是最简
                if(zxgbs==1) res++;
            }
        }
        if(res) cout<<res<<endl;
    }
}
// 64 位输出请用 printf("%lld")