专栏文章

题解：CF2065G Skibidus and Capping

sson_son
CF2065G题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq9x7x3
此快照首次捕获于
2025/12/04 01:21
3 个月前
此快照最后确认于
2025/12/04 01:21
3 个月前
查看原文

思路

可以先考虑一些性质：
  1. 半质数只有 2 种拆分方式，即为 1 ×\times 它自己，p×qp \times q。
  2. lcm⁡(x,y)=x′×y′×gcd⁡(x,y)\operatorname{lcm}(x,y)=x^\prime \times y^\prime \times \gcd(x,y)，其中 x′=x/gcd⁡(x,y)x^\prime=x/\gcd(x,y)，y′=y/gcd⁡(x,y)y^\prime=y/\gcd(x,y)。
发动我们惊人的注意力可以注意到，需要 lcm⁡(x,y)\operatorname{lcm}(x,y) 为半质数时，x′x^\prime，y′y^\prime，gcd⁡(x,y)\gcd(x,y) 中必定有一个是一。（半质数性质）
由此进行分讨：
  1. gcd⁡(x,y)=1\gcd(x,y)=1，且 x′x^\prime，y′y^\prime 都是质数，根据性质 2，反推 x=x′x=x^\prime，y=y′y=y^\prime 且 x≠yx \neq y。(否则 gcd⁡(x,y)=x=y\gcd(x,y)=x=y）
  2. x′x^\prime，y′y^\prime 中较小的为 1，接下来，假设较大的为 x′x^\prime，较小的为y′y^\prime。需要满足 gcd⁡(x,y)\gcd(x,y)，x′x^\prime，yy 都为质数。
注意到，y=gcd⁡(x,y)y=\gcd(x,y)，x=x′×gcd⁡(x,y)=x′×yx=x^\prime \times \gcd(x,y)=x^\prime \times y。惊人发现 xx 为半质数且其中一个质因数为 yy。
看似结束了，实则还有一种。如：x=y=4x=y=4。
  1. x′=y′=1x^\prime=y^\prime=1，x=yx=y 且 xx，yy 为半质数，这样 lcm⁡(x,y)=gcd⁡(x,y)=x=y\operatorname{lcm}(x,y)=\gcd(x,y)=x=y 为半质数。

AC code:

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

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...