CF990G 题解

· · 题解

直接求 \gcd =k 的点对是没法快速求的，所以我们转而求 \gcd 为 k 倍数的点对数量。

一个最朴素的想法就是取出所有点权为 k 倍数的点，然后用并查集合并，扫一遍每个连通块。

如果有 V 个点的点权是 k 的倍数的话，对 k 求一次的复杂度是 O(V) 的。

然后你写了一发这个做法，发现它很神奇地过了）

对于 \le 2\times 10^5 的所有数，因数最多的是 166320=2^4 \times 3^3 \times 5 \times 7 \times 11， 有 160 个因数。

所以对于上述做法，复杂度上界 O(160n) ，可以通过。

#include<bits/stdc++.h>
using namespace std;
const int NR=2e5+10;
#define ll long long
int n,a[NR],flag[NR],fa[NR];
vector<int>g[NR],v[NR];
#define pb push_back

ll f[NR],size[NR];
int get(int x){
    if(fa[x]==x)return x;
    return fa[x]=get(fa[x]);
}
void merge(int x,int y){
    x=get(x);y=get(y);
    if(x==y)return;
    fa[x]=y;size[y]+=size[x];
}
void init(){
    for(int i=1;i<=n;i++)size[i]=1,fa[i]=i;
}

signed main(){
    cin>>n;init();
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        for(int j=1;j<=sqrt(a[i])+0.5;j++)
            if(a[i]%j==0){
                if(j*j==a[i])v[j].pb(i);
                else v[j].pb(i),v[a[i]/j].pb(i);
            }
    }
    for(int i=1,x,y;i<n;i++)
        scanf("%d%d",&x,&y),g[x].pb(y),g[y].pb(x);
    for(int i=1;i<=2e5;i++){
        for(int x:v[i])flag[x]=1;
        for(int x:v[i])
            for(int k:g[x])
                if(flag[k])merge(x,k);
        for(int x:v[i])
            if(fa[x]==x)f[i]+=size[x]*(size[x]+1)/2;
        for(int x:v[i])
            flag[x]=0,size[x]=1,fa[x]=x;
    }
    for(int i=2e5;i>=1;i--)
        for(int j=2;j*i<=2e5;j++)f[i]-=f[i*j];
    for(int i=1;i<=2e5;i++)
        if(f[i])printf("%d %lld\n",i,f[i]);
    return 0;
}