2023-07-31 19:29:29 solution

P9488 ZHY 的生成树

前言

这道题就非常的巧，下午上午上课刚讲完筛法，下午就考到了一个很像筛法的题。当时看到这个数据范围尽往线性做法想了，后面实在想不到就开始想如何带 \(\log\) 做，先拿个 \(60\)pts 再说。

思路

看到这样的求最大生成树，首先先排除真的两两连边跑 Prim，当然你可以通过这样拿到 \(30\)pts，但是我觉得码量太大不如想贪心做法。

一开始想到从大到小枚举每个数的每个因数和因数的倍数计算 \(\gcd\)，但是考虑到这样不一定最优，得把所有情况都枚举出来并且还得排序，不如把 \(n\) 折半，然后从大到小枚举倍数，这样我们可以保证连的边最大并且值就是本身。

如果你直接这么打，显然会连第二个样例都过不了，会发现大了不少，这是为什么呢？因为题目让你求的是一棵树啊，每个点至少要连一条边，如果这样枚举会导致大质数不被连到。那如果你再加个数组判断每个数有没有被连到，还是会发现大了不少，因为树要保证点与点之间的联通性，你直接盲目连会导致最后出现的不是一棵树，而是一片森林。

在我把后面的暴力打完之后，我重新来思考这道题。联通性？那不如直接先把所有点连到 \(1\)，然后再用上面的方法直接改变两条边的连接方式使其仍然联通，也就是判断两个点之间是否已经连过，然后断掉其中一个点连向 \(1\) 的边，建一个两点之间的边。如何判断是否连过？当然是并查集啊！判断两个点是否不经过 \(1\) 联通即可。

\(60\) pts \(Code\)

ll n,ans,fa[10000006];
inline ll find(ll x){
    if(x==fa[x])return x;
    return fa[x]=find(fa[x]);
}
int main(){
    cin>>n;ans=n-1;
    for(ll i=1;i<=n;i++)fa[i]=i;
    for(ll i=n/2;i>1;--i){
        for(ll j=i*2;j<=n;j+=i){
            if(find(i)!=find(j))fa[find(i)]=find(j),ans+=i-1;
        }
    }
    cout<<ans;
}

之后我一直以为瓶颈在并查集，因为我发现去掉并查集后跑的飞快。结果赛后参考了一下题解，发现每次乘的时候不应该一个一个乘，发现有很多次重复，发现如果加的是合数，那肯定前面已经有是你的倍数比你贡献大的连过了，那此时肯定会出现连过的情况。所以我们直接每次乘质数即可，与埃氏筛神似。

\(Code\)

int n,tot,fa[10000006],prime[10000004];
bool vis[10000004];
ll ans;
inline int find(int x){
    if(x==fa[x])return x;
    return fa[x]=find(fa[x]);
}
inline void init(){
    for(int i=2;i<=10000000;i++){
        if(!vis[i])prime[++tot]=i;
        for(int j=1;j<=tot&&i*prime[j]<=10000000;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }
    }
}
int main(){
    cin>>n;  
    ans=n-1;
    init();
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=n/2;i>1;--i){
        for(int j=1;j<=tot&&i*prime[j]<=n;j++){
            if(find(i)!=find(prime[j]*i))fa[find(i)]=find(prime[j]*i),ans+=i-1;
        }
    }
    cout<<ans;
}