题解：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)

的对数。

题目分析：

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

$a_i,a_j$ 都是质数且 $a_i \neq a_j$ ， $(i,j)$ 当然满足条件。
$a_i,a_j$ 中有一个半质数，另一个数是这个数的因数（即 $p,q$ 之一）， $(i,j)$ 也满足条件。
第三种情况是 $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

是否是质数/半质数进行统计和求和。实现方法应该比较多，我使用了树状数组：

CPP

#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;
}

题解：CF2065G Skibidus and Capping

文章操作

简要说明题意：

题目分析：

相关推荐

评论

题解：CF2065G Skibidus and Capping