题意
有一棵有 \(n\) 个节点的树，第 \(i\) 个节点有点权 \(a_i\)。
定义 \(g(x,y)\) 为 \(x\) 到 \(y\) 的树上路径所经过的点的点权 \(\gcd\)。
对于每一个正整数 \(k\in[1,2\times 10^5]\) 求出满足以下条件的 \(x,y\) 的对数:
-
\(1\le x\le y\le n\)
-
\(g(x,y)=k\)
\(1\le n,a_i\le 2\times 10^5\)
Trick 1
显然 \(gcd(x,y)=k\) 是非常难求的，所以我们考虑用莫比乌斯反演，令 \(F(i)\) 表示 \(gcd(x,y)=k\) 的点对个数 \(G(i)\) 表示 \(gcd(x,y)\) 是 \(k\) 的倍数的点对个数。很明显，求出所有 \(G(i)\) 就可以求出所有 \(F(i)\)，即：
Trick 2
考虑求 \(G(i)\)。枚举两端的点权都是 \(i\) 的边，合并两个点，最后计算每个联通块内的点数，任意两个点都是一个合法的点对，所以是 \(x\times (x-1)/2\)，\(x\) 为连通块中点的数量。每条边最多被算 \(160\) 次，即当 \(gcd(u,v)=166320=2^4×3^3×5×7×11\) 时，他有 \(160\) 个因数，他的每个因数都会枚举这条边，但它是小于 \(2e5\) 的拥有最多因数的数，所以枚举 \(G(i)\) 的时间复杂度不超过 \(O(160m)\)
Trick 3
考虑倒着求 \(F(i)\)，很明显当求到 \(F(i)\) 时，所有满足 \(j>i\) 的\(F(j)\) 都已经求出来，那么就会有：
就不用求 \(\mu\) 了
细节：
因为形如 \((i,i)\) 的点对是合法的，所以在输出答案 \(F(i)\) 时还要加上点权为 \(i\) 的点的个数
上代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+50;
int n,a[N],u[N],v[N],tzy;
vector<int> val[N];
int f[N],gs[N],f1,f2;
bool vis[N];
ll G[N];
int find(int x)
{
if(f[x]==x) return x;
return f[x]=find(f[x]);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<n;i++)
{
scanf("%d %d",&u[i],&v[i]);
tzy=__gcd(a[u[i]],a[v[i]]);
for(int j=1;j*j<=tzy;j++)
{
if(tzy%j) continue;
val[j].push_back(i);
if(j^(tzy/j)) val[tzy/j].push_back(i);
}
}
for(int i=1;i<=n;i++)
f[i]=i,gs[i]=1;
for(int i=1;i<=N-50;i++)
{
for(int j=0;j<val[i].size();j++)
{
f1=find(u[val[i][j]]),f2=find(v[val[i][j]]);
if(f1!=f2)
{
G[i]=G[i]-1ll*gs[f1]*(gs[f1]-1)/2-1ll*gs[f2]*(gs[f2]-1)/2;
f[f1]=f2;
gs[f2]+=gs[f1];
G[i]=G[i]+1ll*gs[f2]*(gs[f2]-1)/2;
}
}
for(int j=0;j<val[i].size();j++)
{
f[u[val[i][j]]]=u[val[i][j]];
f[v[val[i][j]]]=v[val[i][j]];
gs[u[val[i][j]]]=1;
gs[v[val[i][j]]]=1;
}
}
for(int i=2e5;i>=1;i--)
{
for(int j=i+i;j<=2e5;j+=i) G[i]-=G[j];
}
for(int i=1;i<=n;i++) G[a[i]]++;
for(int i=1;i<=2e5;i++) if(G[i]) printf("%d %lld\n",i,G[i]);
return 0;
}