题解：CF2065G Skibidus and Capping

· · 题解

思路

可以先考虑一些性质：

  1. 半质数只有 2 种拆分方式，即为 1 \times 它自己，p \times q。

发动我们惊人的注意力可以注意到，需要 \operatorname{lcm}(x,y) 为半质数时，x^\prime，y^\prime，\gcd(x,y) 中必定有一个是一。（半质数性质）

由此进行分讨：

注意到，y=\gcd(x,y)，x=x^\prime \times \gcd(x,y)=x^\prime \times y。惊人发现 x 为半质数且其中一个质因数为 y。

看似结束了，实则还有一种。如：x=y=4。

AC code:

#include<bits/stdc++.h>
using namespace std;
long long _,n,a[200005],sum[200005],ji[200005],jib[200005],ck2[200005],ck[200005],ck3[200005];
inline bool CK(long long x){//是否为质数
    for(long long i=2;i*i<=x;i++){
        if(x%i==0)return 0;
    }
    return 1;
}
inline long long CK2(long long x){//是否为半质数
    long long ans=0;
    for(long long i=2;i*i<=x;i++){
        if(x%i==0 && (ck[i]==0 || ck[x/i]==0))return -1;
    }
    return 1;
}
inline long long CK3(long long x){//若为半质数，它的q,p是多少
    for(long long i=2;i*i<=x;i++){
        if(x%i==0)return i;
    }
    return 0;
}
int main(){
    for(long long i=1;i<=200000;i++)ck[i]=CK(i);
    for(long long i=1;i<=200000;i++){
        if(!ck[i])ck2[i]=CK2(i),ck3[i]=CK3(i);
    }
    scanf("%lld",&_);
    while(_--){
        long long ans=0;
        scanf("%lld",&n);
        for(long long i=1;i<=n;i++){
            sum[i]=ji[i]=jib[i]=0;
            scanf("%lld",&a[i]);
        }
        for(long long i=1;i<=n;i++){
            if(ck[a[i]])ans+=(sum[i-1]-ji[a[i]]),ji[a[i]]++;//第一种分讨
            sum[i]=sum[i-1]+ck[a[i]];
            if(ck2[a[i]]==1)jib[a[i]]++,ans+=jib[a[i]];//第三种分讨
        }
        for(long long i=1;i<=n;i++){//第二种分讨
            if(ck2[a[i]]==1){
                long long t=ck3[a[i]];
                ans+=ji[t]+ji[a[i]/t];
                if(t*t==a[i])ans-=ji[t];
            }
        }
        printf("%lld\n",ans);
    }
}