题解：CF2065G Skibidus and Capping

· · 题解

简要说明题意：

定义满足 x=pq（p,q 均为质数）的数 x 为半质数。现在给出一个长度为 n 的数组 a，求满足 1 \leq i \leq j \leq n,\rm{lcm}(a_i,a_j) 为半质数的 (i,j) 的对数。

题目分析：

注意到符合条件的只有这三种情况：

  3. 第三种情况是 a_i=a_j，a_i 是半质数。

如果 a_i,a_j 都是质数且 a_i=a_j，\textrm{lcm}(a_i,a_j)=a_i，不符合题意。

如果 a_i,a_j 中有一个半质数（记作 x=pq），但另一个数不是这个数的因数（记作 p'），则 \textrm{lcm}(a_i,a_j)=pqp'，不符合题意。

如果 a_i,a_j 至少有一个不属于半质数的合数（记作 t 吧），那么 \textrm{lcm}(a_i,a_j)=t*m，t 已经不能写成 x=pq 的形式了。

那么就比较好做了，预处理所有的质数，在读入时根据 a_i 是否是质数/半质数进行统计和求和。实现方法应该比较多，我使用了树状数组：

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> p;
int markp[200001];
bool semip[200001];
void euler(){
    for(int i=2;i<=200000;++i){
        if(!markp[i]) markp[i]=i,p.push_back(i);
        for(int j=0;j<p.size()&&(long long)p[j]*i<=200000&&p[j]<=markp[i];++j){
            markp[p[j]*i]=p[j];
            if(markp[i]==i) semip[p[j]*i]=true;
        }
    }
}
int C[200001],n,mark[200001],cntp[200001];//C是权值树状数组，mark用于统计质数和半质数，cntp[i]是已经出现的含i的半质数个数
int lowbit(int v){
    return v&(-v);
}
void modify(int x,int v){
    for(;x<=n;x+=lowbit(x)) C[x]+=v;
}
int query(int l,int r){ //[l,r]
    int cnt=0;
    for(--l;l;l-=lowbit(l)) cnt-=C[l];
    for(;r;r-=lowbit(r)) cnt+=C[r];
    return cnt;
}
int main(){
    int T;
    long long cnt;//这答案肯定会爆int
    scanf("%d",&T),euler();
    while(T--){
        scanf("%d",&n),fill(C+1,C+1+n,0),fill(mark+1,mark+1+n,0),fill(cntp+1,cntp+1+n,0),cnt=0ll;
        for(int i=0,temp;i<n;++i){
            scanf("%d",&temp);
            if(markp[temp]==temp) ++mark[temp],modify(temp,1),cnt+=query(1,temp-1)+query(temp+1,n)+cntp[temp];
            if(semip[temp]){
                ++mark[temp],++cntp[markp[temp]],cnt+=mark[markp[temp]]+mark[temp];
                if(markp[temp]^(temp/markp[temp])) cnt+=mark[temp/markp[temp]],++cntp[temp/markp[temp]];
            }
        }
        printf("%lld\n",cnt);
    }
    return 0;
}