https://ac.nowcoder.com/acm/contest/327/I

这题有点坑的就是，这题其实和本场比赛上一题一点关系都没有……

直接分解质因子以后暴力n²枚举就可以，下面来分析一下这么做的时间复杂度:

• 对于每个数分解质因子，sqrt(n)的复杂度，打素数表可以更快。2000*20=40000
• 对于每个数枚举其他数，由于分解的时候质因子是有序的，所以对两个数可以归并排序的方法线性合并质因子。
• 小知识点：对于1e9以内的数，一般不同的质因子个数不超过10个
• 所以对于合并的复杂度，不会超过o(20)，2000*2000*20=80000000
• 总复杂度小于1e8，且常数极小，可以接受

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
int n,ans=0;
vector<pii> a[2002];
int main()
{
    scanf("%d",&n);
    for(int j=1;j<=n;j++)
    {
        int k;
        scanf("%d",&k);
        for(int i=2;i*i<=k;i++)
        {
            int res=0;
            if(k%i==0)
            {
                while(k%i==0)
                {
                    k/=i;
                    res++;
                }
                a[j].push_back(make_pair(i,res));
            }  
        }
        if(k>1) a[j].push_back(make_pair(k,1));
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            int l=0,r=0,tmp=1;
            auto &aa=a[i];
            auto &bb=a[j];
            while(l<aa.size() && r<bb.size())
            {
                if(aa[l].first<bb[r].first) tmp*=aa[l++].second+1;
                else if(aa[l].first>bb[r].first) tmp*=bb[r++].second+1;
                else tmp*=aa[l++].second+bb[r++].second+1;
            }
            while(l<aa.size()) tmp*=aa[l++].second+1;
            while(r<bb.size()) tmp*=bb[r++].second+1;
            if(tmp<=10) ans++;
        }
    }
    printf("%d\n",ans);
}